====== CodeChef March Challenge 2021 ======

[[https://www.codechef.com/MAY21B|比赛链接]]

===== An Interesting Sequence =====

==== 题意 ====

给定 $T$ 个询问，每次询问给定 $k$，求

$$
\sum_{i=1}^{2k}\text{gcd}(k+i^2,k+(i+1)^2)
$$

==== 题解 ====

$$
(k+i^2,k+(i+1)^2)=(k+i^2,2i+1)=(4k+4i^2,2i+1)=(4k+1+(2i+1)\ast(2i-1),2i+1)=(4k+1,2i+1)
$$

于是题目转化为求

$$
\sum_{i=1}^{2k}\text{gcd}(4k+1,2i+1)
$$

记 $f(n)=\sum_{i=1}^n\text{gcd}(n,i),g(n)=\sum_{i=1}^n\text{gcd}(n,i)[2\mid i]$，于是有

$$
g(4k+1)+g(4k+1)=\sum_{i=1}^{2k}\text{gcd}(4k+1,2i)+\sum_{i=1}^{2k}\text{gcd}(4k+1,4k+1-2i)=f(4k+1)-(4k+1)
$$

于是有

$$
\sum_{i=1}^{2k}\text{gcd}(4k+1,2i+1)=f(4k+1)-1-g(4k+1)=f(4k+1)-1-\frac{f(4k+1)-(4k+1)}2
$$

接下来考虑计算 $f$，有

$$
f(n)=\sum_{d\mid n} d\sum_{i=1}^n[\text{gcd}(n,i)=d]=\sum_{d\mid n} d\sum_{i=1}^n[\text{gcd}(\frac nd,\frac id)=1]=\sum_{d\mid n} \varphi(\frac nd)d
$$

于是可以 $O(k\log k)$ 预处理。

<hidden 查看代码>
<code cpp>
const int MAXK=1e6,MAXM=MAXK*4+5;
int prime[MAXM],phi[MAXM];
LL f[MAXM];
int main()
{
	int p_cnt=0;
	phi[1]=1;
	_for(i,2,MAXM){
		if(!phi[i])prime[p_cnt++]=i,phi[i]=i-1;
		for(int j=0;j<p_cnt&&i*prime[j]<MAXM;j++){
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	_for(i,1,MAXM){
		for(int j=1;i*j<MAXM;j++)
		f[i*j]+=1LL*j*phi[i];
	}
	int T=read_int();
	while(T--){
		int k=read_int();
		enter(f[4*k+1]-1-(f[4*k+1]-(4*k+1))/2);
	}
	return 0;
}
</code>
</hidden>