Input file: div.in
Output file: div.out
Time limit: 1 seconds
Memory limit: 128 megabytes
给定 m 个不同的正整数 a1; a2; :::; am，请对 0 到 m 每一个 k 计算，在区间 [1; n] 里有多少正整数
是 a 中恰好 k 个数的约数。
Input
第一行包含两个正整数 n; m，分别表示区间范围以及 a 数组的大小。
第二行包含 m 个不同的正整数 a1; a2; :::; am，表示 a 数组。
Output
输出 m + 1 行，每行一个整数，其中第 i 行输出 k = i 的答案。
Examples
| div.in | div.out |
| 10 3 4 6 7 |
4 4 1 1 |
| 5 1 8 |
2 3 |
Notes
| 测试点编号 | m | n; ai |
| 1 | = 5 | ≤ 1000 |
| 2 | = 50 | ≤ 1000 |
| 3 | = 200 | ≤ 1000 |
| 4 | = 1 | ≤ 109 |
| 5 | = 1 | ≤ 109 |
| 6 | = 1 | ≤ 109 |
| 7 | = 200 | ≤ 109 |
| 8 | = 200 | ≤ 109 |
| 9 | = 200 | ≤ 109 |
| 10 | = 200 | ≤ 109 |
分析
我们可以枚举a1~am的约数,枚举量为sqrt(n),因为如果n/i=0,那么n/(n/i)=0,用一个数组记录一下就行了，但是根据题目数据数组开不了这么大怎么办，有两种方法：
1.开一个hash表，因为约数个数是远远小于sqrt(n)*200的，所以hash表开到6000000就够了。
2.用离散化
代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int p=6000011; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,m,num,sum; int a[201],cnt[p],nxt[p],head[p]; struct data { int x,c; }b[p]; inline int h(int x) {return x%p;} inline void insert(int x) { int u=h(x); for(int i=head[u];i;i=nxt[i]) if(b[i].x==x) { cnt[b[i].c]--; cnt[++b[i].c]++; return; } nxt[++num]=head[u]; b[num].x=x; b[num].c=1; cnt[1]++; head[u]=num; } int main() { freopen("div.in","r",stdin); freopen("div.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++) a[i]=read(); for(int i=1;i<=m;i++) for(int j=1;j*j<=a[i]&&j<=n;j++) { if(a[i]%j==0) { insert(j); if(j*j!=a[i]&&(a[i]/j)<=n) insert(a[i]/j); } } for(int i=1;i<=num;i++) if(b[i].c!=0) sum++; printf("%d ",n-sum); for(int i=1;i<=m;i++) printf("%d ",cnt[i]); }
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m; long long a[1010],ans,maxa=-100,cnt=0,kk=0,tot=1,b[1010100],tt=0,anc[1010100],c[1010010]; int main() { freopen("div.in","r",stdin); freopen("div.out","w",stdout); memset(c,0,sizeof(c)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%lld",&a[i]); maxa=max(maxa,a[i]); } if(m!=1&&maxa<=3000) { for(int i=1;i<=m;i++) for(int j=1;j*j<=a[i];j++) { if(a[i]%j==0&&j<=n) { c[j]++; int t=a[i]/j; if(t!=j&&t<=n) c[t]++; } } for(int i=0;i<=m;i++) { ans=0; for(int j=1;j<=n;j++) if(c[j]==i) ans++; printf("%lld ",ans); } return 0; } if(m==1) { for(int j=1;j*j<=a[1];j++) { if(a[1]%j==0&&j<=n) { ans++; int t=a[1]/j; if(t!=j&&t<=n) ans++; } } printf("%lld ",n-ans); printf("%lld",ans); return 0; } for(int i=1;i<=m;i++) for(int j=1;j*j<=a[i];j++) { if(a[i]%j==0&&j<=n) { b[++cnt]=j; int t=a[i]/j; if(t!=j&&t<=n) b[++cnt]=t; } } sort(b+1,b+cnt+1); kk=0;b[cnt+1]=b[cnt]+100; for(int i=1;i<=cnt;i++) { if(b[i]==b[i+1]) { tot++; continue; } else { c[kk++]=tot; tot=1; } } for(int i=1;i<=m;i++) { anc[i]=0; for(int j=0;j<kk;j++) if(c[j]==i) anc[i]++; tt+=anc[i]; } printf("%lld ",n-tt); for(int i=1;i<=m;i++) printf("%lld ",anc[i]); fclose(stdin); fclose(stdout); return 0; }