LINK：简单题

以前写过弱化版的 不过那个实现过于垃圾 少预处理了一个东西。

这里写一个实现比较精细了。

最后可推出式子：\(\sum_{T=1}^nsum(\frac{n}{T})\sum_{x|T}(\frac{T}{x})^kx^k\mu(\frac{T}{x})^2\mu(x)\)

其中 \(sum(x)=\sum_{i=1}^{x}\sum_{j=1}^{x}(i+j)^k\)

先看前面的那项 由于是完全积性函数先筛出\(i^k\)复杂度可近乎是O(n)的。

考虑上面的式子怎么求？再设\(w_x=\sum_{i=1}^x(i+x)^k\)

显然 \(w_x=w_{x-1}+(2x-1)^k+(2x)^k-x^k\)

显然 \(sum_x=sum_{x-1}+2w_x-(2x)^k\)

后面那项 考虑积性函数筛出 可以发现当其中的质因子p的指数>=3时为0.

那么每次可以特判一下是否为2 简单计算一下即可。

有点卡空间 所以就把 sum w 前缀和数组给整到一块了/cy

const int MAXN=10000010,maxn=2000010;

int T,n,top,k;

int p[maxn];

bitset<MAXN<<1>v;

ui s[MAXN<<1],b[MAXN<<1];

inline ui ksm(ui b,int p)

{

	ui cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b;

		p=p>>1;b=b*b;

	}

	return cnt;

}

inline void prepare()

{

	int m=n<<1;b[1]=s[1]=1;

	rep(2,m,i)

	{

		if(!v[i])

		{

			p[++top]=i;

			s[i]=ksm(i,k);

			b[i]=s[i]*i-s[i];

		}

		rep(1,top,j)

		{

			if(p[j]>m/i)break;

			v[i*p[j]]=1;

			s[i*p[j]]=s[i]*s[p[j]];

			if(i%p[j]==0)

			{

				if(i/p[j]%p[j]!=0)b[i*p[j]]=s[p[j]]*s[p[j]]*p[j]*(-1)*b[i/p[j]];

				break;

			}

			b[i*p[j]]=b[i]*b[p[j]];

		}

	}

	ui las=0;

	rep(1,n,i)

	{

		b[i]+=b[i-1];

		s[i]=las+s[2*i-1]+s[i<<1]-s[i];

		las=s[i];s[i]=-s[i<<1]+s[i-1]+2*s[i];

	}

}

int main()

{

	//freopen("1.in","r",stdin);

	get(T);get(n);get(k);

	prepare();

	while(T--)

	{

		get(n);ui ans=0;

		int w1,ww;

		for(int i=1;i<=n;i=ww+1)

		{

			w1=n/i;ww=n/w1;

			ans+=s[w1]*(b[ww]-b[i-1]);

		}

		printf("%u\n",ans);

	}

	return 0;

}