「最大公约数」题解

题目大意

小菜的妹妹小诗就要读小学了！正所谓计算机要从娃娃抓起，小菜决定在幼儿园最后一段轻松的时间里教妹妹编程。
　　小菜刚教完gcd即最大公约数以后，一知半解的妹妹写了如下一段代码：
　　 sum:=0;
　　 for i:=1 to n-1 do
　　 for j:=i+1 to n do sum:=sum+gcd(i,j)

　　显然这个程序的效率是很低的，小明打算写一个更强的程序，在求出sum的同时比妹妹跑的更快。

输入格式

1 2	第一行一个整数t，即表示有t组数据　　接下来t行，每行一个整数n

输出格式

1	t行，每行一个整数，表示n所对应的sum值

样例输入

1
2
3

2
10
100

样例输出

1
2

67
13015

数据范围

【数据规模】
　　20%数据t≤100,n≤100
　　40%数据t≤1000,n≤2000
　　100%数据t≤10000,n≤1000000

题解

题目目的是求 $1$ ~ $n$ 内任意两个数的 $gcd$ 之和，先放着。

假设 $gcd(n,i)=k$ ，则 $gcd(\frac{n}{k},\frac{i}{k})=1$

即假设 $gcd(\frac{n}{k},x)=1$ ，则 $gcd(n,x*k)=k$

因为 $k$ 的取值是 $n$ 的因子，

所以 $gcd(n,x\times k)=k$ 中 $x$ 的个数 $\times k$ 为答案

所以题目转换成了 $\sum_{i\mid n}^{n} i\times \varphi(n/i)$

就设 $f_i=gcd(1,n)+gcd(2,n)+...+gcd(n,n)$

那么 $ans_i=ans_{i-1}+f_i$

先用线筛筛出 $\varphi(i)$ （OI-Wiki上讲的挺清楚的，不会可以看看）

筛的过程中顺便处理掉 $f$ 和 $ans$

答案就是 $ans_n$

代码

#include <cstdio>
#define N 1000005
using namespace std;
int pr[70000],cnt;
int T,n,phi[N],t,mx;
long long sum[N],f[N];
bool p[N];int a[N];
void init(int mx)
{
	for (int i=2;i<=mx;++i) {
		if (!p[i]) pr[++cnt]=i,phi[i]=i-1;
		for (int j=1;j<=cnt;++j) {
			int x=i*pr[j];if (x>mx) break;
			p[x]=1,phi[x]=phi[i]*(pr[j]-(i%pr[j]>0));
		}
	}for (int i=1;i<=mx;++i) {
		for (int j=i+i;j<=mx;j+=i)
			f[j]+=i*phi[j/i];
		sum[i]=f[i]+sum[i-1];
	}return ;
}
int main()
{
	scanf("%d",&T);
	for (int i=1;i<=T;++i)
		scanf("%d",&a[i]),
			mx=(a[i]>mx)?a[i]:mx;
	init(mx);
	for (int i=1;i<=T;++i)
		printf("%lld\n",sum[a[i]]);
}