题意

给一个\(n\)，计算

\[\sum_{i=1}^{n}\sum_{j=1}^{i-1}[gcd(i + j, i - j) = 1]\]

题解

令\(a = i - j\)

要求

\[\sum_{i=1}^{n}\sum_{j=1}^{i-1}[gcd(i + j, i - j) = 1]\]

即求

\[\sum_{i=1}^{n}\sum_{a=1}^{i-1}[gcd(2*i - a, a) = 1]\]

根据\(gcd\)的性质，即

\[\sum_{i=1}^{n}\sum_{a=1}^{i-1}[gcd(2*i, a) = 1]\]

所以要求的就是\(1\)到\(i-1\)中，与\(2*i\)互质的数的个数。

令\(sum[i]\)为\(i\)的欧拉函数\(\phi\)的前缀和。结论是，对于奇数，答案就是\(sum[i]/2\)，对于偶数，答案是\(sum[i]\)。

与\(2*i\)互质的数的个数，和\(\phi(i)\)（与\(i\)互质的数的个数）有什么关系呢？

如果\(i\)是奇数，那么\(1\)到\(i-1\)中与\(i\)互质的所有数中的奇数，都与\(2*i\)互质。

如果\(i\)是偶数，那么\(1\)到\(i-1\)中与\(i\)互质的所有数，都与\(2*i\)互质。

现在的问题是，为什么\(1\)到\(i-1\)中，与\(i\)互质的数中，奇数占一半？

因为对于任何一个奇数，小于它的和它互质的数，是以\(k\)和\(n-k\)的形式成对出现的。这两个数必然一奇一偶。

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define FOPI freopen("in.txt", "r", stdin)#define FOPO freopen("out.txt", "w", stdout)using namespace std;typedef long long LL;const int maxn = 2e7 + 5;int phi[maxn], prime[maxn];LL sum[maxn];int tot = 0;void getPhi(int n){    for (int i = 2; i <= n; i++) phi[i] = 0;    phi[1] = 1;    for (int i = 2; i <= n; i++)    {        if (!prime[i])        {            prime[++tot] = i;            phi[i] = i-1;        }        for (int j = 1; j <= tot; j++)        {            if (i*prime[j] > n) break;            prime[i*prime[j]] = 1;            if (i % prime[j] == 0)            {                phi[i*prime[j]] = prime[j] * phi[i];                break;            }            else phi[i*prime[j]] = (prime[j]-1)*phi[i];        }    }}void init(int n){    getPhi(n);    for (int i = 1; i <= n; i++)        if (i % 2 == 1)            sum[i] = sum[i-1] + phi[i] / 2;        else            sum[i] = sum[i-1] + phi[i];}int t, n;int main(){    init(2e7);    scanf("%d", &t);    for (int ca = 1; ca <= t; ca++)    {        scanf("%d", &n);        printf("%lld\n", sum[n]);    }}