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
| 测试点编号 | (m) | (n,a_i) |
|---|---|---|
| (1) | (=5) | (≤1000) |
| (2) | (=50) | (≤1000) |
| (3) | (=200) | (≤1000) |
| (4) | (=1) | (≤10^9) |
| (5) | (=1) | (≤10^9) |
| (6) | (=1) | (≤10^9) |
| (7) | (=200) | (≤10^9) |
| (8) | (=200) | (≤10^9) |
| (9) | (=200) | (≤10^9) |
| (10) | (=200) | (≤10^9) |
题目有点绕，看了好半天
昨天这套题做的太草了
前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( "
%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