题目链接 https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1188
【题目描述】
给出一个数N，输出小于等于N的所有数，两两之间的最大公约数之和。相当于求
Ans=∑i=1i<n∑j=i+1j<ngcd(i,j)Ans=∑i=1i<n∑j=i+1j<ngcd(i,j)
Input
第1行：1个数T，表示后面用作输入测试的数的数量。(1 <= T <= 50000)
第2 - T + 1行：每行一个数N。(2 <= N <= 5000000)
Output
共T行，输出最大公约数之和。
Input示例
3
10
100
200000
Output示例
67
13015
143295493160
【思路】
51Nod 1040是这题的简化版，求的是
∑i=1i<ngcd(i,n)∑i=1i<ngcd(i,n)
有公式 ∑i=1i<ngcd(i,n)=∑i=1,i|ni<ni×phi(ni)∑i=1i<ngcd(i,n)=∑i=1,i|ni<ni×phi(ni)
把它用到这道题里面去 Ans=∑i=1n∑j=1n−1gcd(i,j)Ans=∑i=1n∑j=1n−1gcd(i,j)
=∑i=2i<n∑j=1j<igcd(i,j)=∑i=2i<n∑j=1j<igcd(i,j)
=∑i=2i<n∑t=1,t|it<it×phi(it)=∑i=2i<n∑t=1,t|it<it×phi(it)
按照这个式子去计算，当然不能直接像这样直接枚举每个 ii，然后再枚举每个 ii 的因子 tt ，通过观察可以发现这个式子枚举的是 [2,n][2,n] 所有数除了自己之外的所有因子，所以换个角度出发，直接枚举每个因子 tt，然后把 tt 的若干倍作为 ii 来使用，就可以像埃氏筛那样在 O(nlogn)O(nlogn) 的时间内预处理所有答案了 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int maxn = 5000005;int phi[maxn];
ll ans[maxn];void phi_table(int n) {for (int i = 2; i <= n; ++i) phi[i] = 0;phi[1] = 1;for (int i = 2; i <= n; ++i) {if (0 == phi[i]) {for (int j = i; j <= n; j += i) {if (0 == phi[j]) phi[j] = j;phi[j] = phi[j] / i * (i - 1);}}}for(int i=1;i<=n;++i){for(int j=2;j*i<=n;++j){ans[i*j]+=(ll)phi[j]*(ll)i;}}for(int i=1;i<=n;++i) ans[i]+=ans[i-1];
}int main(){phi_table(maxn-1);int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);printf("%lld\n",ans[n]);}return 0;
}