Euler's Totient Function

样例输入

3  
1 6  
1 100  
1 1000000

样例输出

12  
3044  
303963552392

解题思路：

不管是素数还是合数，初始值都是它本身。

j为素数，f[j]=j-1，相当于f[j]=j/i*(i-1),i=j

埃筛，j+=i,i为j的因子，f[j]=f[j]/i*(i-1),先除防止溢出。

最后输出的数可能会很大，用long long 类型。

#include<stdio.h>
#define ll long long
#define N 3000009
ll f[3000005]={};
void init(){
	int i,j,k=1;
    f[1]=1;
	for(i=2;i<N;i++){
		if(f[i]==0){//素数 
			for(j=i;j<N;j+=i){
				if(f[j]==0)f[j]=j;//初始值 
				f[j]=f[j]/i*(i-1); 
			}
		}
		f[i]+=f[i-1];
	}
}
void Sol(){
	int m,n;
	scanf("%d%d",&m,&n);
	printf("%lld\n",f[n]-f[m-1]);
}
int main(){
	int T;
	scanf("%d",&T);
	init();
	while(T--){
		Sol();
	}
	return 0;
}

欧拉函数

样例输入
1
29
100000000
0
样例输出
0
28
40000000

解题思路：按题意模拟即可

#include<stdio.h>
#define ll long long
int Judge(int n){
	int i,flag=1;
	for(i=2;i*i<=n;i++){
		if(n%i==0){
			flag=0;
			break;
		}
	}
	return flag;
}
int main(){
	ll n;
	while(scanf("%lld",&n)&&n!=0){
		int i;
		ll cnt;
		if(Judge(n))cnt=n-1;
		else if(n==1)cnt=1;
		else{
			cnt=n;
			for(i=2;i*i<=n;i++){
			  if(n%i==0&&Judge(i)){
			     cnt=cnt/i*(i-1);//防止溢出 
				 while(n%i==0)n/=i; 
			  }
		    }
		    if(n>1)cnt=cnt/n*(n-1);
		}
		printf("%lld\n",cnt);
	}
}