POJ 1284 Primitive Roots 欧拉函数

题目链接：http://poj.org/problem?id=1284

题意

定义一个数原根x：{x^i(mod p) =1,2,…,p-1}，先给出素数p，要求p得原根个数

题解

这里用到了一个定理：
如果p有原根，则p的原根个数为Euler[Euler[p]]

代码

typedef long long ll;

map<ll,ll> prime_factor(ll t)
{
	map<ll,ll> ret;
	for(int i=2;i*i<=t;i++)
	{
		while(t%i==0) { ++ret[i];t/=i; }
	}
	if(t!=1) ret[t]=1;
	return ret;
}

ll Euler (ll t)
{
	ll ret=t;
	map<ll,ll> fac=prime_factor(t);
	for(map<ll,ll>::iterator i=fac.begin();i!=fac.end();i++)
		ret=ret*(i->first-1)/i->first;
	return ret;
}

void solve()
{
	ll n;
	while(scanf("%lld",&n)!=EOF && n)
		printf("%lld\n",Euler(Euler(n)));
}