题目1 : 数论五·欧拉函数
时间限制: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
解答：
开始没看提示的时候想着用辗转相除，然后枚举，找出最小的fn，当数据特别大的时候，时间复杂度很高，然后提交TLE，超时了，代码也分享一下：
1 #include"iostream" 2 #define MAX 50000 3 4 using namespace std; 5 6 int gcd(int a,int b) 7 { 8 if(b==0) 9 return a; 10 return gcd(b,a%b); 11 } 12 13 int solve(int l,int r) 14 { 15 int fn[MAX]; 16 int fn_date,min,loc; 17 for (int i = l; i <= r; i++){ 18 fn_date = 0; 19 for(int j=1;j<i;j++) 20 if(gcd(i,j)==1) 21 fn_date++; 22 fn[i]=fn_date; 23 //cout << fn[i] << endl; 24 } 25 26 min = fn[l]; 27 loc = l; 28 for (int i = l; i <= r; i++) 29 if (fn[i]<min) 30 { 31 min = fn[i]; 32 loc = i; 33 } 34 35 return loc; 36 } 37 38 int main() 39 { 40 int k,l,r; 41 cin>>l>>r; 42 43 cout<<solve(l,r); 44 system("pause"); 45 46 }
改了的递推AC版本：
1 #include"iostream" 2 #define MAX 5000000 3 4 using namespace std; 5 6 bool isPrime[MAX+1]; 7 int primeList[MAX+1]; 8 int phi[MAX]; 9 int primeCount = 0; 10 11 int solve(int l, int r) 12 { 13 for (int i = 0; i <= MAX; i++) 14 isPrime[i] = true, phi[i] = 1; 15 16 for (int i = 2; i <= MAX; i++) 17 { 18 if (isPrime[i]) { 19 primeList[++primeCount] = i; 20 phi[i] = i - 1; 21 } 22 23 for (int j = 1; j <= primeCount; j++) { 24 if (i*primeList[j] > MAX) break; 25 isPrime[i*primeList[j]] = false; 26 if (i%primeList[j] == 0) { 27 phi[i*primeList[j]] = phi[i] * primeList[j]; 28 break; 29 } 30 else phi[i*primeList[j]] = phi[i] * (primeList[j] - 1); 31 } 32 } 33 34 35 int min = l; 36 for (int i = l; i <= r; i++) 37 if (phi[i]<phi[min]) 38 { 39 min = i; 40 } 41 42 return min; 43 } 44 45 int main() 46 { 47 int k, l, r; 48 cin >> l >> r; 49 50 cout << solve(l, r); 51 system("pause"); 52 53 }