HDU 6706 huntian oy

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=1e6+10,mod=1e9+7;
 5 const int inv2=500000004,inv3=333333336;
 6 int phi[maxn],n,ans;
 7 
 8 vector<int> p;bool np[maxn];
 9 map<int,int> Phi;
10 
11 void init(){
12     phi[1]=1;
13     for(int i=2;i<maxn;++i){
14         if(!np[i]){
15             p.push_back(i);
16             phi[i]=i-1;
17         }
18         for(int j=0;j<p.size()&&p[j]*i<maxn;++j){
19             np[i*p[j]]=true;
20             if(i%p[j]==0){
21                 phi[i*p[j]]=phi[i]*p[j];
22                 break;
23             }
24             phi[i*p[j]]=phi[i]*(p[j]-1);
25         }
26     }
27     for(int i=1;i<maxn;++i)
28         phi[i]=(1ll*phi[i]*i%mod+phi[i-1])%mod;
29 }
30 int read(){
31     int x=0;char c=getchar();
32     for(;!isdigit(c);c=getchar());
33     for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
34     return x;
35 }
36 void Write(int x){
37     if(x<=0)return;
38     Write(x/10);putchar(x%10+‘0‘);
39 }
40 void write(int x){
41     if(x==0)putchar(‘0‘);
42     else Write(x);
43 }
44 int Sum2(int n){
45     int ret=n;
46     ret=(ll)ret*inv2%mod;
47     ret=(ll)ret*(n+1)%mod;
48     return ret;
49 }
50 int Sum3(int n){
51     int ret=Sum2(n),tmp=(2ll*n+1)%mod;
52     ret=(ll)ret*inv3%mod;
53     ret=(ll)ret*tmp%mod;
54     return ret;
55 }
56 int phii(int n){
57     if(n<maxn)return phi[n];
58     if(Phi.count(n))return Phi[n];
59     int ret=Sum3(n);
60     for(int i=2,r,tmp;i<=n;i=r+1){
61         r=min(n,n/(n/i));
62         tmp=(ll)phii(n/i)*(Sum2(r)-Sum2(i-1))%mod;
63         ret-=tmp;
64         if(ret<0)ret+=mod;
65         if(ret>=mod)ret-=mod;
66     }
67     return Phi[n]=ret;
68 }
69 void solve(){
70     n=read();read();read();
71     Phi.clear();
72     ans=(phii(n)-1+mod)%mod;
73     ans=(ll)inv2*ans%mod;
74     write(ans);puts("");
75 }
76 int main(){
77     init();
78     int T;scanf("%d",&T);
79     for(;T--;)solve();
80     return 0;
81 }