题意：求
题解：这题...数据范围是真小...
研究一下这一表达式，发现gcd(i,j)=1表示i，j互质，那么互质肯定能想到欧拉函数，可是欧拉函数要求j<i，那么我们变化一下：显然原矩阵是对称的，所以可以转化一下，变成
（注意到后面-1是为了防止（1,1）被重复统计）
那么发现答案就是
公式挂掉的地方见博客：https://blog.csdn.net/lleozhang/article/details/83419761
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
int pri[];
int phi[];
bool used[];
int tot=;
int n;
void init()
{
scanf("%d",&n);
if(n==)
{
printf("0\n");
return;
}
n--;
int ans=;
for(int i=;i<=n;i++)
{
if(!used[i])
{
pri[++tot]=i;
phi[i]=i-;
}
for(int j=;j<=tot&&i*pri[j]<=n;j++)
{
used[i*pri[j]]=;
if(i%pri[j]==)
{
phi[i*pri[j]]=phi[i]*pri[j];
break;
}else
{
phi[i*pri[j]]=phi[i]*(pri[j]-);
}
}
ans+=phi[i];
}
ans*=;
ans++;
printf("%d\n",ans);
}
int main()
{
init();
return ;
}