• 周四. 12月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

欧拉函数

admin

11月 28, 2021

#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 }

View Code

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注