提交时间:2022-08-05 19:09:35

运行 ID: 57585

#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; }