首页 > 代码库 > 数论五·欧拉函数

数论五·欧拉函数

#1298 : 数论五·欧拉函数

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi和小Ho有时候会用密码写信来互相联系,他们用了一个很大的数当做密钥。小Hi和小Ho约定了一个区间[L,R],每次小Hi和小Ho会选择其中的一个数作为密钥。

小Hi:小Ho,这次我们选[L,R]中的一个数K。

小Ho:恩,小Hi,这个K是多少啊?

 

小Hi:这个K嘛,不如这一次小Ho你自己想办法算一算怎么样?我这次选择的K满足这样一个条件:

假设φ(n)表示1..n-1中与n互质的数的个数。对于[L,R]中的任意一个除K以外的整数y,满足φ(K)≤φ(y)且φ(K)=φ(y)时,K<y。

也即是K是[L,R]中φ(n)最小并且值也最小的数。

小Ho:噫,要我自己算么?

小Hi:没错!

小Ho:好吧,让我想一想啊。

<几分钟之后...>

小Ho:啊,不行了。。感觉好难算啊。

小Hi:没有那么难吧,小Ho你是怎么算的?

小Ho:我从枚举每一个L,R的数i,然后利用辗转相除法去计算[1,i]中和i互质的数的个数。但每计算一个数都要花好长的时间。

小Hi:你这样做的话,时间复杂度就很高了。不妨告诉你一个巧妙的算法吧:

输入

第1行:2个正整数, L,R,2≤L≤R≤5,000,000。

输出

第1行:1个整数,表示满足要求的数字K

样例输入
4 6
样例输出
4


<style>pre.cjk { font-family: "Droid Sans Fallback", monospace } p { margin-bottom: 0.25cm; line-height: 120% } a:link { }</style>
欧拉函数:小于n的正整数中与n互质的数的个数。

性质:

(1) n为素数,则φ(n) = n - 1

显然,由于n为素数,1~n-1n都只有公因子1,因此φ(n) = n - 1

(2) n = p^kp为素数(即n为单个素数的整数幂),则φ(n) = (p-1)*p^(k-1)

因为np的整数幂,因此所有p的倍数和n都不互质。小于np的倍数一共有p^(k-1)-1个,因此和n互质的个数为:

p^k-1- (p^(k-1)-1) = p^k - p^(k-1) = (p-1)*p^(k-1)
(3)
pq互质,则φ(p*q)
= φ(p) * φ(q)

由以上性质,可以推出以下定理:

(1) pn的约数,则φ(n*p) = φ(n) * p

pn的约数,且p为质数。则我们可以将n表示为p^k*mm表示其他和p不同的质数的乘积。

显然有p^km互质,则:

φ(n)
= φ(p^k)*φ(m) = (p-1)*p^(k-1)*φ(m)
φ(n*p)
= φ(p^(k+1))*φ(m) = (p-1)*p^k*φ(m) = (p-1)*p^(k-1)*φ(m) * p = 
φ(n) * p

(2) p为不为n的约数,则φ(n*p) = φ(n) * (p-1)

p不为n的约数,因此pn互质,所以φ(n*p) = φ(n) * φ(p) = φ(n)*(p-1)


有了这些定理,就可以用Eular筛法求出欧拉函数了。
因为每个素数都可以直接计算,每个合数都会被筛掉,所以每个数都会计算到。


 1 #include<set>
 2 #include<map>
 3 #include<queue>
 4 #include<stack>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<string>
 8 #include<vector>
 9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<iostream>
13 #include<algorithm>
14 #define maxn 5000010
15 using namespace std;
16 bool su[maxn];
17 int f[maxn];
18 int Eular[maxn];
19 int main()
20 {
21   freopen("!.in","r",stdin);
22   freopen("!.out","w",stdout);
23   int l,r,sum=0;
24   scanf("%d%d",&l,&r);
25   for(int i=1;i<=r;i++) su[i]=1;
26   for(int i=2;i<=r;i++){
27     if(su[i])f[++sum]=i,Eular[i]=i-1;
28     for(int j=1;j<=sum;j++){
29       if(f[j]*i>r) break;
30       su[f[j]*i]=0;
31       if(i%f[j]==0){
32     Eular[i*f[j]]=Eular[i]*f[j];
33     break;
34       }
35       else Eular[i*f[j]]=Eular[i]*(f[j]-1);
36     }
37   }
38   int zd=1999999999,id;
39   for(int i=l;i<=r;i++)
40     if(Eular[i]<zd) zd=Eular[i],id=i;
41   printf("%d",id);
42   return 0;
43 }

 


数论五·欧拉函数