过样例0pts求条

#include<bits/stdc++.h>
using namespace std;
#define uint int
int n,k,t;
const int N=1e7+5;
uint pw(uint x,int k){
	uint ans=1;
	while(k){
		if(k&1)ans=ans*x;
		k>>=1,x=x*x;
	}
	return ans;
}
uint f[2*N],g[2*N];
uint s[N];
int pri[N],cnt;
void F(int n){
	f[1]=1,g[1]=1;
	for(int i=2;i<=n;i++){
		if(!g[i]){
			g[i]=pw(i,k);
			pri[++cnt]=i,f[i]=i-1;
		}
		for(int j=1;j<=cnt;j++){
			if(pri[j]>n/i)break;
			g[i*pri[j]]=g[i]*g[pri[j]];
			if(i%pri[j]){
				f[i*pri[j]]=f[i]*f[pri[j]];
			}
			else{
				if((i/pri[j])%pri[j]){
					if(i!=pri[j])f[i*pri[j]]=f[i/pri[j]]*f[pri[j]*pri[j]];
					else f[i*i]=-i;
				}
				else{
					f[i*pri[j]]=0;
				}
				break;
			}
		}
	}
	for(int i=2;i<=n;i++)f[i]=f[i]*g[i],f[i]+=f[i-1],g[i]+=g[i-1];
}
void S(int n){
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]+g[2*i]-g[i]+g[2*i-1]-g[i];
	}
}
void sol(){
	cin>>n;
	int l=1,r;
	uint ans=0;
	for(;l<=n;){
		r=n/(n/l);
		ans+=(f[r]-f[l-1])*s[n/l];
		l=r+1;
	}cout<<ans<<'\n';
}
int main(){
	cin>>t>>n>>k;
	F(2*n);S(n);
	while(t--)sol();
	return 0;
}