题目1 : 数论五·欧拉函数
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
- 样例输入
-
4 6
- 样例输出
-
4
描述
小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
题意：如上所说，即是K是[L,R]中φ(n)最小并且值也最小的数，本来以为会很难很难的题目，因为时间限制10000ms，然后看了一下欧拉函数！就……
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
using namespace std;
int eular(int n) //欧拉函数
{
int ret=1,i;
for(i=2; i*i<=n; i++)
{
if(n%i==0)
{
n/=i,ret*=i-1;
while(n%i==0)
n/=i,ret*=i;
}
}
if(n>1)ret*=n-1;
return ret;
}
int s[5000005];
int main()
{
int r,l;
cin>>r>>l;
int maxx=0xfffff,ji=0;
for(int i=r; i<=l; i++)
{
s[i]=eular(i);
if(s[i]<maxx)
{
maxx=s[i];
ji=i;
}
}
printf("%d\n",ji);
return 0;
}