1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include<bits/stdc++.h> using namespace std;
typedef long long ll; #define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO; template <class T=int> T rd(){ T s=0; int f=0; while(!isdigit(IO=getchar())) if(IO=='-') f=1; do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return f?-s:s; }
const int N=2e5+10,P=1e9+7;
int T,n,k,x; int mk[N],notpri[N],pri[N],pc,w[N]; ll qpow(ll x,ll k=P-2) { ll res=1; for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P; return res; } int s[N],F[N],S[N],A[N];
int main(){ w[1]=1; rep(i,2,N-1) { if(!notpri[i]) pri[++pc]=i,w[i]=-1; for(int j=1;j<=pc && 1ll*i*pri[j]<N;++j) { notpri[i*pri[j]]=1; if(i%pri[j]==0) { w[i*pri[j]]=0; break; } w[i*pri[j]]=-w[i]; } } for(int i=2;i*i<N;++i) for(int j=i*i;j<N;j+=i*i) mk[j]=1; rep(i,1,N-1) if(!mk[i]) rep(j,1,(N-1)/i) F[i*j]=(F[i*j]+i*w[j]+P)%P; T=rd(),k=rd(),x=rd(); rep(i,1,N-1) S[i]=(S[i-1]+F[i]*qpow(i,1ll*k*x))%P; rep(i,1,N-1) A[i]=(A[i-1]+qpow(i,k))%P; rep(i,1,N-1) A[i]=qpow(A[i],x); rep(kase,1,T) { n=rd(); ll ans=0; for(int i=1,j;i<=n;i=j+1) { j=n/(n/i); ans=(ans+1ll*(S[j]-S[i-1])*A[n/i])%P; } ans=(ans%P+P)%P; printf("%lld\n",ans); } }
|