[算进] BZOJ 2818（欧拉函数）

Problem

ACwing 题目地址

BZOJ 题目地址

Solution

一眼莫反，许多年前好像用莫反做过。但是在其他大佬的博客里Get到了一种用欧拉函数的快速算法，写一下。

定理

[sum_{i=1}^n sum_{j=1}^n [gcd(i,j)=1] = (sum_{i=1}^n 2*φ(i)) - 1 ]

很好理解。减去的 (1) 是多算的一个 ((1,1))。

让后就可以切爆这题了。

Code

Talk is cheap.Show me the code.

#include<bits/stdc++.h>
#define int long long
using namespace std;
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^48); ch=getchar(); }
	return x * f;
}
const int N = 1e7+7;
int n,tot,ans;
int phi[N],p[N],sum[N];
bool vis[N];
void MakePhi() {
	phi[1] = 1;
	for(int i=2;i<=n;++i) {
		if(!vis[i]) {
			p[++tot] = i; phi[i] = i-1;
		}
		for(int j=1;j<=tot&&i*p[j]<N;++j) {
			if(i%p[j] == 0) {
				vis[i*p[j]] = 1, phi[i*p[j]] = phi[i]*p[j]; break;
			} else vis[i*p[j]] = 1, phi[i*p[j]] = phi[i] * phi[p[j]];
		}
	}
	for(int i=1;i<=n;++i)
		sum[i] = sum[i-1] + phi[i];
}
signed main()
{
	n = read();
	MakePhi();
	for(int i=1;i<=tot&&p[i]<=n;++i) {
		ans += 2 * sum[n/p[i]] - 1;
	}
	printf("%lld
",ans);
	return 0;
}

Summary

这个定理很重要！！！