Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
57585 | 陶俊宸 | 迟到的生日 | C++ | 解答错误 | 20 | 0 MS | 280 KB | 818 | 2022-08-05 19:09:35 |
#include<iostream> int n,m,st[10000001],pn[700000],cnt,sum,fs[10000001]={0,1}; long long ans1=1,ans2=1; void dfs(int v,int f,bool flag){ int now=v*f; if(flag) fs[now]=fs[v]*fs[f]; else{ int ins=now;fs[now]=1; for(int i=0;ins>=now/ins;i++){ int sum=0; while(!(ins%pn[i])){ sum++; ins/=pn[i]; } fs[now]*=sum+1; } if(ins>1) fs[now]*=ins; } ans1+=fs[now]; if(now<m) ans2+=fs[now]; for(int i=0;pn[i]*now<=n;i++){ if(pn[i]==f) dfs(now,pn[i],0); if(pn[i]>f) dfs(now,pn[i],1); } } int main(){ scanf("%d %d",&m,&n); for(int i=2;i<=n;i++){ if(!st[i]){ pn[cnt++]=i; fs[i]=2; } for(int j=0;i*pn[j]<=n;j++){ st[i*pn[j]]=1; if(!(i%pn[j])) break; } } for(int i=0;i<cnt;i++) dfs(1,pn[i],1); printf("%lld",ans1-ans2); return 0; }