题目：
求(sum_{i=1}^{n}{sum_{j=1}^{i-1}{[gcd(i+j,i-j)=1]}})
数据范围：(Tleq 10^5,nleq 2*10^7)
分析：
一看数据范围这么大，基本上就要预处理，或者推公式求。
其实如果找规律的话，也可以找出。下面讲一下如何推导。
推导：
令 (a=i-j),
根据拓展欧几里得，有：
(gcd(i+j,a)=gcd(2*i-a,a)=gcd(2*i,a))
原式转化为：
(sum_{i=1}^{n}{sum_{a=1}^{i-1}{[gcd(2*i,a)=1]}})
因为是 (2*i)，所以对 (i) 的奇偶性进行讨论。
当 (i) 为偶数时，与 (i) 互质的数和 (2*i) 也互质，所以结果为 (varphi(i))；
当 (i) 为奇数时，只有与 (i) 互质的奇数才会和 2*i 互质，所以结果为 (varphi(i)/2)；
那么为什么当 (i) 为奇数时，与 (i) 互质的数是奇，偶成对出现的呢？
证明如下：
首先证明 如果【1】(gcd(a,b)=1)，那么 (gcd(a,a-b)=1);
反证法：
假设存在数 (k!=1)，使得 (gcd(a,a-b)=k)，即 (k|(a-b))，(k|a)，所以 (k|b)。
所以 (gcd(a,b)=k)，出现矛盾，即证。
（以下可以忽略）
通过这个性质还可以求出小于等于n且与n互质的数的和，如下：
[ans=egin{cases}
frac{varphi(n)*n}{2} & ngeq 2\
1 & n=1
end{cases}]
由性质【1】易证。
所以当 (i) 为奇数时，如果 (j) 和它互质，若 (j) 为奇数，则 (i-j) 必为偶数；若 (j) 为偶数，则 (i-j) 必为奇数。
所以奇数和偶数成对出现。
代码：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N=2e7+5;
vector<int>prime;
bool vis[N];
ll phi[N],sum[N];
void euler()
{
phi[1]=1;
for(int i=2;i<=N-5;i++)
{
if(!vis[i])
{
prime.pb(i);
phi[i]=i-1;
}
for(int j=0;j<prime.size()&&i*prime[j]<=N-5;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
for(int i=1;i<=N-5;i++)
{
if(i&1)
sum[i]=sum[i-1]+phi[i]/2;
else
sum[i]=sum[i-1]+phi[i];
}
}
int main()
{
int t,n;
euler();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(n<0)
printf("0
");
else
printf("%lld
",sum[n]);
}
return 0;
}