此题可以拓展为 \(\sum\limits^n_{i=1}\sum\limits^m_{j=1}\gcd(i,j)\)
结论是 \(\sum\limits^{\min(n,m)}_{d=1}\varphi(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor\)
#include <bits/stdc++.h>
#define rei register int
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, ll mod){long long res = 1; while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod; b >>= 1; } return res;}
using namespace std;
const int maxn = 100000;
ll p[maxn], vis[maxn], cnt;
ll phi[maxn];
void get_phi(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
p[cnt++] = i;
phi[i] = i - 1; // phi(p) = p -1
}
for (int j = 0; i * p[j] <= n; j++) {
int m = i * p[j];
vis[m] = 1;
if (i % p[j] == 0) {
phi[m] = p[j] * phi[i];
break;
}
else {
phi[m] = (p[j] - 1) * phi[i];
}
}
}
}
int main()
{
int n;
cin >> n;
get_phi(maxn);
ll ans = 0;
for (int i = 1; i <= n; i++) {
int t = n / i;
ans += phi[i] * t*t;
}
cout << ans << endl;
return 0;
}
标签:phi,ch,GCD,int,SUM,P2398,maxn,ll,define
From: https://www.cnblogs.com/CYLSY/p/17017651.html