欧拉函数
概述
欧拉函数就是对于一个正整数\(n\)，小于\(n\)且和\(n\)互质的正整数(包括1)的个数，记作\(φ(n)\)。
欧拉函数的通式:
\(φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)\)
其中\(p_1, p_2,...,p_n\)为\(n\)的所有质因数，\(n\)是不为\(0\)的整数。\(φ(1)=1\)(唯一和1互质的数就是1本身)。
性质
- 当\(m,n\)互质时，有\(\phi(m \times n)= \phi(m)* \phi(n)\)；
- 若\(i%p==0\)，有\(\phi(i \times p) = p \times \phi(i)\)；
- 对于互质\(x\)与\(p\)，有\(x^{\phi(p)}≡1（mod \ p)\),因此x的逆元为\(x^{\phi(p)-1}\)，即欧拉定理。
（特别地，当p为质数时，\(\phi(p)=p-1\),此时逆元为\(x^{p-2}\)，即费马小定理）
- 当\(n\)为奇数时，\(\phi(2n)=\phi(n)\)
- 若\(x\)与\(p\)互质，则\(p-x\)也与\(p\)互质，因此小于\(p\)且与\(p\)互质的数之和为\(\phi(x) \times x/2\);
- \(N>1\)，不大于\(N\)且和\(N\)互素的所有正整数的和是 \(1/2 \times N \times eular(N)\)。
欧拉筛模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | void eular_()//欧拉筛模板
{
memset(vis,true,sizeof(vis));
int cnt=1;
vis[1]=false;
for(int i=2;i<=N-5;i++)
{
if(vis[i]) prime[cnt++]=I;
for(int j=1;j<cnt&&prime[j]*i<=N-5;j++)
{
vis[prime[j]*i]=false;
if(i%prime[j]==0)
{
break;
}
//若i为p[j]的倍数，则i=k*p[j]，
//在和p[j+1]相乘后得出的x=i*p[j+1]=p[j]*k*p[j+1]
//则在i=k*p[j+1]时，由于j从小到大，必定经过之前的p[j]，会重复计算
}
}
}
|
欧拉函数模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | int euler(int x)
{
int ans=x;
for(int i=2;i*i<=x;i++)//模拟（1-p1）*（1-p2）……过程，pi为x的质因数
{
if(x%i==0)
{
ans=ans-ans/i;
}
while(x%i==0)
{
x/=i;
}
}
if(x>1) ans=ans-ans/x;//若x不为1，说明仍有一个质因数没有乘
return ans;
}
|
线性求欧拉函数
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
29 | void euler_()
{
memset(vis,true,sizeof(vis));
memset(phi,0,sizeof(phi));
int cnt=1;
vis[1]=false;
phi[1]=1;//特判1,gcd(1,1)=1
for(int i=2;i<=N-5;i++)
{
if(vis[i])
{
prime[cnt++]=i;
phi[i]=i-1;
}
for(int j=1;j<cnt&&prime[j]*i<=N-5;j++)
{
vis[prime[j]*i]=false;
if(i%prime[j]==0)
{
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
phi[prime[j]*i]=phi[i]*phi[prime[j]];
//若i为p[j]的倍数，则i=k*p[j]，
//在和p[j+1]相乘后得出的x=i*p[j+1]=p[j]*k*p[j+1]
//则在i=k*p[j+1]时，由于j从小到大，必定经过之前的p[j]，会重复计算
}
}
}
|
例1.HDU2824 The Euler function
题目描述
The Euler function phi is an important kind of function in number theory, (n) represents the amount of the numbers which are smaller than n and coprime to n, and this function has a lot of beautiful characteristics. Here comes a very easy question: suppose you are given a, b, try to calculate (a)+ (a+1)+....+ (b)
输入格式
There are several test cases. Each line has two integers a, b (2<a<b<3000000).
输出格式
Output the result of (a)+ (a+1)+....+ (b)
输入样例
输出样例
题解
线性求欧拉函数模板题
代码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 | #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e6+10;
int phi[N];
bool vis[N];
int prime[N];
int sum[N];
void eular_()//欧拉筛模板
{
memset(vis,true,sizeof(vis));
memset(phi,0,sizeof(phi));
int cnt=1;
vis[1]=false;
phi[1]=1;//特判1,gcd(1,1)=1
for(int i=2;i<=N-5;i++)
{
if(vis[i])
{
prime[cnt++]=i;
phi[i]=i-1;
}
for(int j=1;j<cnt&&prime[j]*i<=N-5;j++)
{
vis[prime[j]*i]=false;
if(i%prime[j]==0)
{
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
phi[prime[j]*i]=phi[i]*phi[prime[j]];
//若i为p[j]的倍数，则i=k*p[j]，在和p[j+1]相乘后得出的*p[j+1]=p[j]*k*p[j+1]
//则在i=k*p[j+1]时，由于j从小到大，必定经过之前的p[j]，会重复计
}
}
}
int main()
{
int a,b;
eular_();
while(cin>>a>>b)
{
ll ans=0;
for(int i=a;i<=b;i++) ans+=phi[i];
cout<<ans<<endl;
}
return 0;
}
|
例2.HDU 2588 GCD
题目描述
The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.
输入格式
The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.
输出格式
For each test case,output the answer on a single line.
输入样例
输出样例
题解
当\(M\)为\(1\)时，易知答案为\(N\)，当\(M>1\)时，可以确定满足条件的数一定时\(N\)大于\(M\)的约数，如果\(x\)不能整除\(N\)，则\(gcd(x,N)=1<M\)，我们知道\(N\)的约数(设为\(x\))和\(N\)的最大公约数为\(x\)，那是否本题只有N的约数满足条件呢？显然不是，数\(x*k\)(\(k\)为满足条件的某些数)与\(N\)的约数同样为\(x\)，倒推一下，当\(gcd(N，x \times k)=x\)时，有\(gcd(N/x，k)=1\)，即\(k\)满足与\(N/x\)互质时满足\(N\)与\(x \times k\)的最大公约数为\(x\)，于是本题就变成了就\(1-N/x\)内，与\(N/x\)互质的数的个数，用欧拉函数求即可
代码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 | #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5;
ll eular(ll x)
{
ll ans=x;
for(int 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;
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll ans=0;
ll n,m;
cin>>n>>m;
int i;
for(i=1;i*i<n;i++)
{
if(n%i==0)
{
if(i>=m)
{
ans+=eular(n/i);
}
if(n/i>=m)
{
ans+=eular(i);
}
}
}
if(i*i==n&&i>=m) ans+=eular(i);
cout<<ans<<endl;
}
return 0;
}
|
例3.HDU phi
题目描述
给出若干个正整数n，请你求出最小的m，使得φ(m)≥n。
输入格式
本题有多组输入。
第一行一个正整数T表示数据组数
接下来T行每行一个正整数n
数据保证\(1≤T≤104,1≤n≤106\)。
输出格式
共T行，每行一个数代表对应的答案
输入样例
输出样例
代码
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 | #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e6+10;
int phi[N-5];
bool vis[N-5];
int prime[N-5];
struct node
{
int pos;
int val;
friend bool operator < (const node x,const node y)//对输入进行处优先处理n小的输入并记录
{
return x.val<y.val;
}
}node[10005];
int ans[10005];
int t;
void euler()
{
int now=1;
memset(vis,false,sizeof(vis));
memset(phi,0,sizeof(phi));
vis[1]=true;
phi[1]=1;
int cnt=0;
for(int i=1;i<=N-10;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;j<=cnt&&prime[j]*i<=N-10;j++)
{
vis[prime[j]*i]=true;
if(i%prime[j]==0)
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*phi[prime[j]-1];
}
while(phi[i]>=node[now].val&now<=t)
{
ans[node[now].pos]=i;
now++;
}
if(now>t) return ;
}
}
int main()
{
euler();
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>node[i].val;
node[i].pos=i;
}
sort(node+1,node+t+1);
euler();
for(int i=1;i<=t;i++)
cout<<ans[i]<<endl;
return 0;
}
|