divisors 数学

divisors 数学

给定(m)个不同的正整数(a_1, a_2,cdots, a_m)，请对(0)到(m)每一个(k)计算，在区间([1, n])里有多少正整数是(a)中恰好(k)个数的约数。

极度考验语文能力的题面。

套路一般分解质因数，但是我们发现分解质因数之后统计会很麻烦，又发现(m)，(a_i)的所有约数个数又很小，所以我们索性将(m)个数分别都预处理出所有可能的约数分解形式丢进栈，之后直接sort栈，线性统计答案即可。

另外，我们发现([1,n])每一个数都只能被计算一次，所以在区间([1, n])里有多少正整数是(a)中恰好0个数的约数的个数即为(n-sum)

#include <cstdio>
#include <iostream>
#include <cmath>
#include <stack>
#include <algorithm>
int s[10000010],s_top;
int res[202];
int n,m,a[202];
int main(){
    scanf("%d %d", &n, &m);
    for(int i=1;i<=m;++i) scanf("%d", &a[i]);
    for(int i=1;i<=m;++i){
        int tmp=(int)sqrt(a[i]);
        for(int j=1;j<=tmp;++j)
            if(a[i]%j==0) s[++s_top]=j,s[++s_top]=a[i]/j;
        if(tmp*tmp==a[i]) --s_top;
    }
    std::sort(s+1, s+1+s_top);
    int cur_cnt=1;
    for(int i=2;i<=s_top;++i){
        if(s[i]>n) break;
        if(s[i-1]==s[i])
            ++cur_cnt;
        else{
            ++res[cur_cnt];
            cur_cnt=1;
        }
    }
    ++res[cur_cnt];
    int sum=0;
    for(int i=1;i<=m;++i) sum+=res[i];
    printf("%d
", n-sum);
    for(int i=1;i<=m;++i) printf("%d
", res[i]);
    return 0;
}