欧拉函数模版

博主链接

求一个数的欧拉函数

ll phi(ll x){		//求1~n与n互质的个数   //   phi(1323)=phi(3^3*7^2)=1323*(1-1/3)*(1-1/7)
	ll i, ans = x;
	for (i = 2; i*i <= x; i++){
		if (x%i == 0)
			ans = ans - ans / i;		
		while(x%i == 0)
			x /= i;
	}
	if (x > 1)
		ans = ans - ans / x;
	return ans;
}

递推求欧拉函数

ll _phi(ll x) {	//递推求欧拉函数   利用了欧拉函数的积性 
//如果b质数  a%b!=0  phi(a*b) = phi(a)*b - phi(a)
//当b是质数,a%b==0,phi(a*b)=phi(a)*b 
	if (x == 0) return 0;
	ll res = 1, t = x;
	for (ll i = 2; i <= (ll)sqrt(1.*x); i++) {
		if (t%i == 0) {
			res *= (i - 1);
			t /= i;
			while (t%i == 0) {
				res *= i;
				t /= i;
			}
		}
		if (t == 1) break;
	}
	if (t > 1) { res *= (t - 1); }
	return res;
}

递推欧拉函数打表

ll phi[maxn]; 
void init()
{
	for(int i=1;i<=maxn;i++)
		phi[i] = i;
	for (int i = 2; i*i < maxn; i++){  //最大素因子表
		if (phi[i] == i){
			for (int j = i * i; j < maxn; j += i){
				phi[j] = i;
			}
		}
	}
	phi[1] = 1;
	for (int i = 2; i < maxn; i++){
		if ((i / phi[i]) % phi[i] == 0){
			phi[i] = phi[i / phi[i]] * phi[i];    //当b是质数,a%b==0,phi(a*b)=phi(a)*b 
		}
		else {
			phi[i] = phi[i / phi[i]] * (phi[i] - 1);  //如果b质数  a%b!=0  phi(a*b) = phi(a)*b - phi(a) 
		}
	}
}

 

全部评论

相关推荐

寿命齿轮:实习就一段还拉了,项目一看就不是手搓,学历也拉了,技术栈看着倒是挺好,就是不知道面试表现能咋样。 不过现在才大三,争取搞两端大厂实习,或者一个纯个人项目+一段大厂,感觉秋招还是未来可期。
投递美团等公司10个岗位
点赞 评论 收藏
分享
10-24 11:10
山西大学 Java
若梦难了:哥们,面试挂是很正常的。我大中厂终面挂,加起来快10次了,继续努力吧。
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务