首页 > 代码库 > LYDSY模拟赛day2 Divisors
LYDSY模拟赛day2 Divisors
/*注意分解质因数,如果i是,那么n/i也是,这样就可以解决分解质因数的时间问题了当 k ≥ 1 时,只有这些数的约数才会对答案产生贡献。求出 m 个数的所有不超过 n 的约数,去重后统计即可。求出 k = 1 到 m 的所有答案后,剩下的数字个数就是 k = 0的答案。时间复杂度 O(m2√a)*/#include<cstdio>#include<algorithm>const int N=205;int n,m,i,a[N],cnt,b[1000000],f[N];void add(int n){for(int i=1;i<=n/i;i++)if(n%i==0)b[++cnt]=i,b[++cnt]=n/i;}int cal(int d){ int t=0; for(int i=1;i<=m;i++)if(a[i]%d==0)t++; return t;}int main(){ freopen("div.in","r",stdin);freopen("div.out","w",stdout); scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d",&a[i]),add(a[i]); std::sort(b+1,b+cnt+1); for(i=1;i<=cnt;i++)if(b[i]<=n&&b[i]!=b[i-1])f[cal(b[i])]++; f[0]=n; for(i=1;i<=m;i++)f[0]-=f[i]; for(i=0;i<=m;i++)printf("%d\n",f[i]); fclose(stdin);fclose(stdout); return 0;}
LYDSY模拟赛day2 Divisors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。