- #include <bits/stdc++.h>
- using namespace std;
- #define LL long long
- const int maxn=1e6+10;
- const LL mod=1e9+7;
- int phi[maxn], p[maxn+1];
- bool check[maxn];
- int phi_and_prime_table()
- {
- phi[1]=1;
- int sz=0;
- for(int i=2;i<maxn;i++)
- {
- if(!p[i]) p[++sz]=i,phi[i]=i-1;
- for(int j=1;j<=sz&&p[j]<=maxn/i;j++) // 注意这个等号不能丢 因为这个 wa 了很多发 p[maxn+1] 数组大小 + 1 可以这么写 不然就老老实实 if break 或者加个 LL
- {
- p[i*p[j]]=1;
- if(i%p[j]==0) {
- phi[i*p[j]]=phi[i]*p[j];break;
- }
- phi[i*p[j]]=phi[i]*(p[j]-1);
- }
- }
- return sz;
- }
- #define vii vector<int>
- vii fac[maxn];
- void getfactor(LL x)
- {
- vii &f=fac[x];
- for(int i=1;(LL)p[i]*p[i]<=x;i++)
- {
- if(x%p[i]==0)
- {
- f.push_back(p[i]);
- while(x%p[i]==0) x/=p[i];
- }
- }
- if(x!=1)f.push_back(x);
- }
- LL cal(int now,LL cur,LL n,vii &f)
- {
- if(now==f.size())return 0;
- LL r=0;
- for(int i=now;i<f.size();i++)
- {
- r+=n/(cur*f[i])-cal(i+1,cur*f[i],n,f);
- }
- return r;
- }
- int main() {
- #ifdef shuaishuai
- freopen("in.txt","r",stdin);
- #endif // shuaishuai
- int t;
- scanf("%d",&t);
- phi_and_prime_table();
- for(int i=2;i<maxn;i++){
- getfactor(i);
- }
- for(int cas=1;cas<=t;cas++)
- {
- LL n;
- scanf("%lld",&n);
- LL ans=0;
- for(LL i=1;i*i<n;i++)
- {
- ans+=n/i-cal(0,1,n/i,fac[i])-phi[i];
- assert(ans>=0);
- }
- printf("Case #%d: %lld\n",cas,(ans*2+1)%mod);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2805789.html