Divisors

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

Input

第一行包含两个正整数\(n, m\)，分别表示区间范围以及\(a\)数组的大小。
第二行包含\(m\)个不同的正整数\(a_1,a_2, ..., a_m\)，表示\(a\)数组。

Output

输出\(m+1\)行，每行一个整数，其中第\(i\)行输出\(k=i\)的答案。

Example

输入 #1

\(10\) \(3\)
\(4\) \(6\) \(7\)

输出 #1

\(4\)
\(4\)
\(1\)
\(1\)

输入 #2

\(5\) \(1\)
\(8\)

输出 #2

\(2\)
\(3\)

Scoring

题目有点绕，看了好半天
昨天这套题做的太草了

前3个点做法：

暴力枚举\(1\)到\(n\)每个数，看看它是\(a\)里几个数的约数

复杂度\(O(nm)\)

第四到第六个点做法：

因为只有一个\(a_i\)，所以枚举\(a_i\)的约数，这些是\(k=1\)时的答案，剩下的就是\(k=0\)的

复杂度\(O(\sqrt{a_i})\)

正解：

看一下数据范围，\(n\)跟\(a_i\)都太大了开不起数组，所以大概率对\(m\)下手

可以把每个\(a_i\)的约数全部求出来，然后sort，这样所有相同的约数都会挤在一起

然后扫一遍统计个数，放到数组ans里（ans[i] == x表示能被\(a\)数组中\(i\)个数整除的数有\(x\)个

以样例1为例：

4的约数：1,2,4，6的约数：1,2,3,6，7的约数：1,7

把这堆数排序之后：1,1,1,2,2,3,4,6,7

有3个1，ans[3]++，2个2，ans[2]++，1个3，ans[1]++，以此类推

最后用\(n\)减去\(\sum_{i=1}^n{ans_i}\)就是ans[0]了

贴代码（不是我的）：

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e7 + 3;
int cnt , k[MAXN] , m , x , n;
int ans[203];
int main(){
    scanf( "%d%d" , &n , &m );
    for( int i = 1 ; i <= m ; i ++ ){
        scanf( "%d" , &x );
        for( int j = 1 ; j * j <= x ; j ++ ){//找出x的因数放到k数组里
            if( x % j == 0 ){
                k[++cnt] = x / j;
                k[++cnt] = j;
            }
            if( j * j == x)
                cnt --;
        }
    }
    sort( k + 1 , k + cnt + 1 );
    int i = 2 , last = k[1] , tot = 1;
    while( i <= cnt && k[i] <= n ){//扫一遍队列
        if( k[i] != last ){//不一样了
            ans[tot] += 1;//停止计算
            last = k[i];//重新开始
            tot = 1;
        }
        else tot ++;
        i ++;
    }
    ans[tot] += 1;//不要漏掉
    int sum = 0;
    for( int i = 1 ; i <= m ; i ++ )
        sum += ans[i];
    printf( "%d" , n - sum );//算ans[0]
    for( int i = 1 ; i <= m ; i ++ )
        printf( "\n%d" , ans[i] );
    return 0;
}

闲话：

昨天爆零了，口区

A题C题MLE，B题传文件的时候系统自动给我重命名了，导致测评姬找不到文件，不知道为啥

A题（就是这题）的MLE还是因为我检查的时候脑子抽了给数组多安了一个0，然后C题是算错

不然预计得分100+40+40

底层群众不敢重测，加上到现在oj上题目都没有放上去，所以也不知道几分不敢乱贴（虽然也没人看），从别人博客转了一个代码过来，批注是自己加工的

参考博客链接：https://blog.csdn.net/weixin_43823476/article/details/87308177

最后是关于计算ans[0]的问题，我自己想出来的做法是在约数放进数组之后，在数组中再添加\(1\)~\(n\)的数各一个，最后统计时把ans[tot]++改成ans[tot-1]++，效果应该一样但是绕了个大弯orz

Divisors

原文：https://www.cnblogs.com/Sheffield/p/13489767.html