\[\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^{t}f(\gcd(i,j))\gcd(i,j) \]\[\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^{t}\mu(\gcd(i,j))^{2}\gcd(i,j) \]\[\sum_{k=1}^{n}k^{t+1}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}(i+j)^{t}\mu(k)^{2}[\gcd(i,j)==1] \]\[\sum_{k=1}^{n}k^{t+1}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}(i+j)^{t}\mu(k)^{2}\sum_{d|\gcd(i,j)}\mu(d) \]\[\sum_{k=1}^{n}k^{t+1}\mu(k)^{2}\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)d^{t}\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}(i+j)^{t} \]
令 \(kd=T\)。
\[\sum_{T=1}^{n}\sum_{d|T}T^{t}d\mu(\frac{T}{d})\mu(d)^{2}\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}(i+j)^{t} \]令 \(S(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}(i+j)^{t}\)。
\[\sum_{T=1}^{n}S(\lfloor\frac{n}{T}\rfloor)T^{t}\sum_{d|T}d\mu(\frac{T}{d})\mu(d)^{2} \]\[\sum_{T=1}^{n}S(\lfloor\frac{n}{T}\rfloor)T^{t}\sum_{d|T}d\mu(\frac{T}{d})\mu(d)^{2} \]bool _Start;//o.O
// #define DEBUG
#include<ctime>
#include<random>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
namespace IO
{
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
#ifdef DEBUG
#define gc() (getchar())
void pc(const char &c)
{
putchar(c);
}
#else
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
char pbuf[1<<20],*pp=pbuf;
inline void pc(const char &c)
{
if(pp-pbuf==1<<20)
fwrite(pbuf,1,1<<20,stdout),pp=pbuf;
*pp++=c;
}
struct IO{~IO(){fwrite(pbuf,1,pp-pbuf,stdout);}}_;
#endif
TP inline void read(T &x)
{
x=0;static int f;f=0;static char ch;ch=gc();
for(;ch<'0'||ch>'9';ch=gc())ch=='-'&&(f=1);
for(;ch>='0'&&ch<='9';ch=gc())x=(x<<1)+(x<<3)+(ch&15);
f&&(x=-x);
}
TP void write(T x)
{
if(x<0)
pc('-'),x=-x;
static T sta[35],top;top=0;
do
sta[++top]=x%10,x/=10;
while(x);
while(top)
pc(sta[top--]^48);
}
TP_ inline void read(T &x,T_&...y){read(x);read(y...);}
TP void writeln(const T x){write(x);pc('\n');}
TP void writesp(const T x){write(x);pc(' ');}
TP_ void writeln(const T x,const T_ ...y){writesp(x);writeln(y...);}
void writest(const std::string &a){static int i;for(i=0;a[i];i++)pc(a[i]);}
TP inline T max(const T &a,const T &b){return a>b?a:b;}
TP_ inline T max(const T &a,const T_&...b){return max(a,max(b...));}
TP inline T min(const T &a,const T &b){return a<b?a:b;}
TP_ inline T min(const T &a,const T_&...b){return min(a,min(b...));}
TP inline void swap(T &a,T &b){static T t;t=a;a=b;b=t;}
TP inline T abs(const T &a){return a>0?a:-a;}
#undef TP
#undef TP_
}
using namespace IO;
using std::cerr;
using LL=long long;
using ULL=unsigned long long;
using PII=std::pair<int,int>;
using uint=unsigned int;
std::mt19937 rd(time(0));
constexpr int N=1e7+10,M=3e5+10;
constexpr int intinf=0x3f3f3f3f;
constexpr LL LLinf=0x3f3f3f3f3f3f3f3f;
constexpr LL P=998244353;
namespace Lofty
{
int n;
uint k;
int prime[N<<1],pr;
bool v[N<<1];
int mu[N<<1];
uint q[N<<1],s[N<<1],f[N<<1],S[N];
uint qpow(uint a,uint b)
{
uint ans=1;
for(;b;b>>=1,a=a*a)
if(b&1)
ans=ans*a;
return ans;
}
void prepare()
{
mu[1]=1;q[1]=1;f[1]=1;
for(int i=2;i<=n<<1;i++)
{
if(!v[i])
prime[++pr]=i,mu[i]=-1,q[i]=qpow(i,k),f[i]=i-1;
for(int j=1;j<=pr&&prime[j]*i<=n<<1;j++)
{
int tmp=prime[j]*i;
v[tmp]=1;
q[tmp]=q[prime[j]]*q[i];
if(i%prime[j]==0)
{
if(i/prime[j]%prime[j])
f[tmp]=(0u-prime[j])*f[i/prime[j]];
break;
}
f[tmp]=f[i]*f[prime[j]];
mu[tmp]=-mu[i];
}
}
for(int i=1;i<=n<<1;i++)
s[i]=q[i]+s[i-1];
for(int i=1;i<=n;i++)
f[i]=f[i-1]+f[i]*q[i];
S[1]=q[2];
for(int i=2;i<=n;i++)
S[i]=(S[i-1]+s[2*i-1]-s[i]+s[2*i]-s[i]);
}
uint calc(int m)
{
uint ans=0;
for(int l=1,r=0;l<=m;l=r+1)
{
r=m/(m/l);
ans=ans+S[m/l]*(f[r]-f[l-1]);
}
return ans;
}
void work()
{
int T=1;
read(T);
read(n,k);
prepare();
while(T--)
{
read(n);
writeln(calc(n));
}
}
}
bool _End;
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
// #endif
// fprintf(stderr,"%.2lf Mib\n",(&_End-&_Start)/1048576.0);
Lofty::work();
return 0;
}
//O.o