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", n-sum);

    for(int i=1;i<=m;++i) printf("%d\n", res[i]);

    return 0;

}

巴特西

divisors 数学

divisors 数学

最新文章

热门文章