欧拉函数例题

1. 除了(1,0)(1,1)(0,1)三个点的，发现其余可视点gcd(x,y)=1
2. 发现关于(1,1)这条线所有点都是对称的，不妨取下半部分，x<y,此时1<=x<y<=n,这就转化到求与y互质数x的个数,
3. y有多个选择,且y>=2,最后答案从2~N累加起来

求欧拉函数值，就是分解质因数的过程，
1.试除法分解质因数累加和，但是只能求出 $\upsilon(n)$,n又要从2~n遍历，
2. e氏筛O($n*loglogn$)

int prime[maxn];
long long  euler(int n){
	for (int i=2; i<=n; i++) prime[i] = i;
	for (int i=2; i<=n; i++) {
		if (prime[i]==i) {//值没有改变说明还是初始化的值，没有被它可能存在的约数筛掉
		    // i此时是j的质因数,根据欧拉公式累加
			for (int j=i; j<=n; j+=i) {
				prime[j] = prime[j] / i * (i - 1);
			}
		} 
	}
	long long ans = 0;
	for (int i=2; i<=n; i++) ans += prime[i]; 
	return 2*ans+3;
}

3.线性筛，标记合数的最小质因子的同时,根据欧拉函数的2个性质，求欧拉值

• $\upsilon(n)=(p-1)*\upsilon(n/p)$
  ( $p|n$ ~~~ $p^2!|n$ )
• $\upsilon(n) = p*\upsilon(n/p)$
  ($p|n$ ~~~$p^2|n$)

  int tot = 0;//质数的个数
  int prime[maxn];
  int v[maxn];
  int phi[maxn];
  long long euler(int n) {
  	for (int i=2; i<=n; i++) {
  		if ( !v[i] ) {//v[i] == 0 不是合数，则是质数
  			v[i] = i;
  			prime[++tot] = i;
  			phi[i] = i-1;//单个质数的欧拉函数的值为n-1;
  		}
  		// 从i对应的合数开始累加质因子
  		for (int j=1; j<=tot; j++) {
  		    //扫描不大于v[i]的每一个质数，来给合数标记最小质因子
  			if ( prime[j]>v[i] || prime[j]>n/i ) break;
  			v[i * prime[j]] = prime[j];
  			if ( i%prime[j] == 0 ) {
  				phi[i * prime[j]] = phi[i] * prime[j];//v(n) = v(n/p) * p; 	
  			}
  			else {
  				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
  			}
  		}
  	}
  	long long ans = 0;
  	for (int i=2; i<=n; i++) {
  		ans += phi[i];
  	}
  	return 2*ans+3;
  }

  题解：

  #include <iostream>
  using namespace std;
  const int maxn=1e3+10;
  int prime[maxn];
  int v[maxn];
  int phi[maxn];
  /*long long  euler(int n){
  	for (int i=2; i<=n; i++) prime[i] = i;
  	for (int i=2; i<=n; i++) {
  		if (prime[i]==i) {//值没有改变说明还是初始化的值，没有被它可能存在的约数筛掉
  			for (int j=i; j<=n; j+=i) {
  				prime[j] = prime[j] / i * (i - 1);
  			}
  		} 
  	}
  	long long ans = 0;
  	for (int i=2; i<=n; i++) ans += prime[i]; 
  	return 2*ans+3;
  }*/
  //线性筛
  int tot = 0;
  long long euler(int n) {
  	for (int i=2; i<=n; i++) {
  		if ( !v[i] ) {
  			v[i] = i;
  			prime[++tot] = i;
  			phi[i] = i-1;//单个质数的欧拉函数的值为n-1;
  		}
  		// 从i对应的合数开始累加质因子
  		for (int j=1; j<=tot; j++) {
  			if ( prime[j]>v[i] || prime[j]>n/i ) break;
  			v[i * prime[j]] = prime[j];
  			if ( i%prime[j] == 0 ) {
  				phi[i * prime[j]] = phi[i] * prime[j];//v(n) = v(n/p) * p; 	
  			}
  			else {
  				phi[i * prime[j]] = phi[i] * (prime[j] - 1);
  			}
  		}
  	}
  	long long ans = 0;
  	for (int i=2; i<=n; i++) {
  		ans += phi[i];
  	}
  	return 2*ans+3;
  }
  int main() {
  	freopen("a.txt","r",stdin);
  	int times;
  	scanf("%d",&times);
  	int cnt = 0;
  	while (times--) {
  		int n;
  		scanf("%d",&n);
  		// e氏筛
  		printf("%d %d %lld\n",++cnt,n,euler(n));
  	}
  	return 0;
  }