欧拉函数与因数查找 8.2@亿万星辰 AcWing 221

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int Get_phi(int n)
{
	int phi=n;
	for(int i=2;(ll)i*i<=n;++i)
	{
		if(n%i==0) {
			phi=(ll)phi*(i-1)/i;
		while(n%i==0) n/=i; 
		}
	}
	if(n>1) phi=(ll)phi*(n-1)/n;
	return phi;
}
int main()
{
	int n;
	scanf("%d",&n);
	ll ans=0;
	for(int i=1;(ll)i*i<=n;++i)//找出n的所有因数 
	{
		if(n%i==0) {
			ans+=(n/i)*Get_phi(i);//从前往后 
			if(i*i!=n) ans+=i*Get_phi(n/i);//从后往前 
		}
	}
	printf("%lld",ans);
	return 0;
 } 

AcWing 221.龙哥的问题代码实现,今日份学习
全部评论

相关推荐

湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务