根号(n)求单个数欧拉函数-526互联

#define ll long long
ll ola(ll n)	//求正整数n的欧拉函数（类似常规的素数判定）
{
	ll ans=n;
	for(ll i=2;i*i<=n;i++)	//因为和因子有关，所以只需根号n内
	{
		if(n%i==0)	//找到一个因子i
		{
			ans=ans*(i-1)/i;	//减去因子i相关的数
			while(n%i==0) n/=i;	//去除所有的因子i 
		}
	}
	if(n>1) ans=ans*(n-1)/n;	//比如原始n=10，最后一个因子5
	return ans;
}