#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
- 利用欧拉函数的性质，可以在O(N)的时间内求出每个数的函数值。
- 欧拉函数定义: 小于n的正整数中与n互质的数的个数。
- 对于欧拉函数，有一下三个性质：1 若n为素数，则φ(n) = n - 1.
- 2 若n = p^k，p为素数（即n为单个素数的整数幂），则φ(n) = (p-1)*p^(k-1).
- 3 若p和q互质，则φ(p*q) = φ(p) * φ(q).
- 有了这三个性质，我们便能推出两个定理： 若p为质数，n为任意整数：(1) 若p为n的约数，则φ(n*p) = φ(n) * p；
- (2) 若p为不为n的约数，则φ(n*p) = φ(n) * (p-1);
- 于是，据这两条定理，当我们得到一个n时，可以枚举质数p来递推的求解φ(n*p)，这就和欧拉筛是一样的了。
1 #define ll long long 2 #include<algorithm> 3 #include<iostream> 4 #include<iomanip> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cstdio> 8 #include<queue> 9 #include<ctime> 10 #include<cmath> 11 #include<stack> 12 #include<map> 13 #include<set> 14 using namespace std; 15 const int N=5000010; 16 int prim[N],phi[N]; 17 bool is[N]; 18 int gi() { 19 int res=0,f=1; 20 char ch=getchar(); 21 while((ch<'0'||ch>'9')&&ch!='-') ch=getchar(); 22 if(ch=='-') ch=getchar(),f=-1; 23 while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); 24 return res*f; 25 } 26 int solve() { 27 int L=gi(),R=gi(); 28 memset(is,1,sizeof(is)); 29 int cnt=0; 30 for(int i=2;i<=R;i++) { 31 if(is[i]) prim[++cnt]=i,phi[i]=i-1; 32 for(int j=1;j<=cnt&&i*prim[j]<=R;j++) { 33 is[i*prim[j]]=false; 34 if(i%prim[j]==0) { 35 phi[i*prim[j]]=phi[i]*prim[j]; 36 } 37 else phi[i*prim[j]]=phi[i]*(prim[j]-1); 38 } 39 } 40 int k=L; 41 for(int i=L+1;i<=R;i++) 42 if(phi[i]<phi[k]) k=i; 43 return k; 44 } 45 int main() {// please remember :infer other things from one fact 46 47 printf("%d",solve()); 48 return 0; 49 }