POJ 2407 Relatives 欧拉函数

发表于 | 分类于 | 阅读次数:
字数统计: 220 字

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

题意

给出一个数n，求出有多少个数小于n并且与n互质，n的范围为1e9

题解

裸的欧拉函数，具体的内容：
小于n且与n互质的数的个数=n*(1-1/P1)*(1-1/P2)….*(1-1/Pn)，其中Pn为不同的质因数
注意特判1的时候ans=0，不过本题没有卡这个东西

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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(n));
}