大家好，又见面了，我是你们的朋友全栈君。
问题：求[L, R]中K ( 假设φ(n)表示1..n-1中与n互质的数的个数。对于[L,R]中的任意一个除K 以外的整数y，满足φ(K)≤φ(y)且φ(K)=φ(y)时，K<y ),K是[L,R]中φ(n)最小并且值也最小的数。
解：用欧拉函数求解
φ(n)，一般被称为欧拉函数。其定义为：小于n的正整数中与n互质的数的个数。
先了解四个性质：
(1) u mod p 与 p 互质 <=> u 和 p 互质
设 a, b互质, c = a mod b 假设 c 与 b 不互质，则存在着 d >= 1, 使得 c = nd, b = md (d 为b，c 的公约数) 因为 c = a mod b, 所以 a = kb + c 则 a = kmd + nd = (km + n)d 因为 b = md，a = (km + n)d 所以 a，b 不互质，与之前矛盾，假设不成立，所以 b 和 c 互质 所以 a 和 b 互质 => b 和 a mod b 互质 同理 可得 b 和 a mod b 互质 => a 和 b 互质
(2) 若 n 是素数，则 φ(n) = n – 1
这是显然的
(3) 若n = p^k，p为素数（即n为单个素数的整数幂），则φ(n) = (p-1)*p^(k-1)
n 是 p 的整数幂，因此所有 p 的倍数和 n 都不互质。小于 n 的 p 的倍数一共有 p^(k-1)-1 个，因此和 n 互质的个数为：
p^k-1 - (p^(k-1)-1) = p^k - p^(k-1) = (p-1)*p^(k-1)
(4) 若 p 和 q 互质，则 φ(p*q) = φ(p) * φ(q)
对于所有小于 pq 的整数 u，可以表示为 u = aq + r。(a=0,1,2,…,p-1，r=0,1,…,q-1)。
对于u = aq + r, 设R = u mod p，0≤R<q。对于一个固定的r，设a1, a2满足0 <= a1, a2 < p且a1≠a2，有：
u1 = a1*q+r, u2 = a2*q+r， u1-u2=(a1-a2)*q
因为p与q互质，且|a1-a2|<p，则|u1-u2|一定不是p的倍数。
所以对于每一个固定的r，其对应的p个u = a*q+r(a=0,1,2,…,p-1)对mod p来说余数都不相同，即u mod p的结果恰好取遍0,1,…,p-1中的每一个数。
因为 u mod p 与 p 互质 <=> u 和 p 互质
因此对于任意一个确定的 r，与其对应的 p 个 u 中恰好有φ(p)个与 p 互质。
同理，由 u = aq + r 知 r 与 q 互质 <=> u 与 q 互质。因此在0..q-1中恰好有φ(q)个 r 使得 u 与 q 互质。
综上，当 r 与 q 互质的情况下，固定 r 可以得到φ(p)个与p和q都互质的数。
满足条件的 r 一共用φ(q)个，所以一共能找到有φ(p) * φ(q)个与p和q都互质的数。
由此得证：φ(p*q) = φ(p) * φ(q)
所以，
若p为n的约数，则φ(n*p) = φ(n) * p，
若p为不为n的约数，则φ(n*p) = φ(n) * (p-1)
根据这两条，当我们得到一个 n 时，可以枚举质数 p 来递推的求解φ(n*p)
因此我们只需要在欧拉筛代码的基础上做一个小改动，就可以得到递推求解φ(n)的算法：
isPrime[] = true primeList = [] phi = [] // phi[n]表示n的欧拉函数 primeCount = 0 For i = 2 .. N If isPrime[i] Then primeCount = primeCount + 1 primeList[ primeCount ] = i phi[i] = i - 1 // 质数的欧拉函数为p-1 End If For j = 1 .. primeCount If (i * primeList[j] > N) Then Break End If isPrime[ i * primeList[j] ] = false If (i % primeList[j] == 0) Then // primeList[j]是i的约数，φ(n*p) = φ(n) * p phi[ i * primeList[j] ] = phi[i] * primeList[j]; Break Else // primeList[j]不是i的约数，φ(n*p) = φ(n) * (p-1) phi[ i * primeList[j] ] = phi[i] * (primeList[j] - 1); End If End If End For
上源代码
#include <iostream> #include <cstring> #include <algorithm> #define N 5000010 using namespace std; int ou[N]; int main(){ int l,r,min=N-1; cin >> l >> r; for(int i=0;i<=r;i++){ ou[i]=i; } //求欧拉函数 for(int i=2;i<=r;i++){ if(ou[i]==i){ for(int j=i;j<=r;j+=i){ ou[j]=ou[j]/i*(i-1); } } } ou[min]=N; for(int i=l;i<=r;i++){ min=ou[min]>ou[i]?i:min; } cout << min << endl; return 0; }
View Code
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/155244.html原文链接：https://javaforall.net
