鱼C论坛

 找回密码
 立即注册
查看: 3627|回复: 9

题目69:找出一百万以下的n中使得n/φ(n)取到最大的n

[复制链接]
发表于 2015-11-5 15:56:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 欧拉计划 于 2015-11-5 16:13 编辑
Totient maximum

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

QQ20151105-1@2x.png

It can be seen that n=6 produces a maximum n/φ(n) for n ≤ 10.

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

题目:

欧拉函数φ(n)(有时也叫做 phi 函数)可以用来计算小于 n 的数字中与 n 互质的数字的个数。例如,因为 1,2,4,5,7,8 全部小于 9 并且与 9 互质,所以φ(9)=6。

QQ20151105-2@2x.png

可以看出对于n ≤ 10,n=6 时的 n/φ(n) 取到最大值。

找出 n ≤ 1,000,000 的 n 中使得 n/φ(n) 取到最大的 n 值。

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2016-10-16 00:14:20 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2016-10-16 06:48 编辑

Mark一下:
解题的关键:
欧拉函数phi(m):当m>1是,phi(m)表示比m小且与m互质的正整数个数
1、费马定理:a的p-1次方mod p余1。(其中p是素数,a是不能被p整除的正整数。
2、欧拉定理
    2.1 欧拉函数(RSA的证明用到)
          定义:欧拉函数phi(m):当m>1是,phi(m)表示比m小且与m互质的正整数个数
               如:phi(24)=8    (1,5,7,11,13,17,19,23)
          性质:(1)当m为素数时,phi(m)=m-1
                    (2)当m=pq,且p和q是互异的素数,
                         则有:phi(m)=phi(p)*phi(p)=(p-1)(q-1) (这很好用)
                    (3)m=p^e,且p为素数,e为正整数,则
                         phi(m)=p^e-p^(e-1)=(p^(e-1))*(p-1)

          定理:若m=p1^e1*p2^e2....pt^et则:
                phi(m)=m(1-1/p1)(1-1/p2)....(1-1/pt) (pi是素数)
     2.2 欧拉定理
            a^phi(n)=1 mod n
          注:[1] n=p时候,有a^(p-1)=1 mod p,为费马定理
                [2] a^(phi(n)+1)=a mod n
                [3] 若n=pq,p与q为相异素数,取大于0的m,n互质数,有
                    m^(phi(n)+1)=m mod n; m^((p-1)(q-1)+1)=m mod n
欧拉函数的定义:E(k)=([1,n-1]中与n互质的整数个数).
   
     因为任意正整数都可以唯一表示成如下形式:
                     k=p1^a1*p2^a2*……*pi^ai;(即分解质因数形式)
    可以推出:E(k)=(p1-1)(p2-1)……(pi-1)*(p1^(a1-1))(p2^(a2-1))……(pi^(ai-1))
               =k*(p1-1)(p2-1)……(pi-1)/(p1*p2*……pi);
               =k*(1-1/p1)*(1-1/p2)....(1-1/pk)
     ps:在程序中利用欧拉函数如下性质,可以快速求出欧拉函数的值(a为N的质因素)
      若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
第一次写欧拉函数的题,琢磨的半天,最后还是只能按照最开始的想法写......
      欧拉函数PHI(n)表示的是比n小,并且与n互质的正整数的个数(包括1)。比如:
      PHI(1) = 1; PHI(2) = 1; PHI(3) = 2; PHI(4) = 2; ... PHI(9) = 6; ...
要计算一个正整数n的欧拉函数的方法如下:
1. 将n表示成素数的乘积: n = p1 ^ k1 * p2 ^ k2 * ... * pn ^ kn(这里p1, p2, ..., pn是素数)
2. PHI(n) = (p1 ^ k1 - p1 ^ (k1 - 1)) * (p2 ^ k2 - p2 ^ (k2 - 1)) * ... * (pn ^ kn - pn ^ (kn - 1))
              = Mult { pi ^ ki - pi ^ (ki -1) }
证明过程如下:
    1. 容易想到:当n为素数时,PHI(n) = n - 1。因为每个比n小的正整数都和n互素。当n为素数p的k次方时,PHI(n) = p ^ k - p ^ (k - 1)。因为在1到n之间的正整数只有p的倍数和n不互素,这样的数有(p ^ k / p)个(为什么?)。
    2. 如果m和n互素,即GCD(m, n) = 1,那么PHI(m * n) = PHI(m) * PHI(n)。用中国剩余定理可以证明,证明的思路是建立这样一种一一对应的关系(a, b) <-> x,其中正整数a小于m并且gcd(a, m) = 1,正整数b小于n并且gcd(b, n) = 1,正整数x小于m*n并且gcd(m*n, x) = 1。证明过程如下:
    1)根据中国剩余定理,如果m和n互素,那么关于未知量x的方程组x % m = a, x % n = b(0 <= a < m, 0 <= b < n),当0 <= x < m * n时存在并且仅存在一个解。容易证明,如果两个这样的方程组有相同的m, n但是a, b不同,那么他们的解x一定不同。
    2)首先用反正法证明:gcd(m, a) = 1且gcd(n, b) = 1是gcd(m*n, x) = 1的必要条件:假设gcd(a, m) = k > 1,由此可得:a = a' * k; m = m' * k => x = k' * m + a = k' * k * m' + k * a' = k * (k' * m' + a'); 所以gcd(x, m) = k > 1。同理可证,如果gcd(b, n) > 1, 那么gcd(x, n) > 1。所以x和m * n互素的必要条件是a和m互诉且b和n互素。
    3)接下来我们证明充分性:由x % m = a 可以得到x = k * m + a;由欧几里德算法求最大公约数的过程(就不证明了,呵呵,还得想)可以知道gcd(x, m) = gcd(m, a) = 1;同理可得,如果gcd(n, b) = 1那么gcd(x, n) = 1。接下来很容易得到:gcd(m*n, x) = 1。从而证明了充分性。
    4)上面三步的结论表明,数对(a, b)是可以和x建立起一一对应的关系的,所以有多少个不同的(a, b),就有多少个不同的x。
    3.将n分解成素数乘积后,显然对于任意的i, j(i != j)都满足 pi ^ ki和pj ^ kj是互素的,于是可以的到上面的公式。
跟据上面的公式,可以得到关于欧拉函数的递推关系:
假设素数p能整除n,那么
如果p还能整除n / p, PHI(n) = PHI(n / p) * p;
如果p不能整除n / p, PHI(n) = PHI(n / p) * (p - 1);
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-16 00:21:14 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2016-10-16 08:19 编辑

解题思路:
用标记法求解,先生成PHI = [0]*1000000,然后依次用质数(或质数的倍数)替换PHI中的值,直至全部完成。 最后求解max(N/PHI),可以用enumerate函数辅助。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-10-16 08:17:31 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2016-10-16 09:41 编辑

答案:
510510 5.539388020833333
[Finished in 2.9 sec]
  1. def getPrime(n):
  2.     primes = [True]*n
  3.     primes[0], primes[1] = False, False
  4.     for (i, prime) in enumerate(primes):
  5.         if prime:
  6.             for j in range(i*i,n,i):
  7.                 primes[j] = False
  8.     primelist = []
  9.     for (k, trueprime) in enumerate(primes):
  10.         if trueprime:
  11.             primelist.append(k)
  12.     return primelist

  13. def philist(n):
  14.     primelist = getPrime(n)
  15.     PHI = [0]*(n+1)
  16.     PHI[0], PHI[1] = -1, -1
  17.     for eachprime in primelist:
  18.         PHI[eachprime] = eachprime - 1
  19.     for i in range(len(primelist)):
  20.         p = primelist[i]
  21.         for k in range(p*p,n+1,p):
  22.                 PHI[k] = PHI[int(k/p)]*(p-1)
  23.         for j in range(p*p,n+1,p*p):
  24.             PHI[j] = PHI[int(j/p)]*p
  25.     return PHI
  26. plist = philist(1000001)

  27. maxn, maxnphi = 0, 0
  28. for i in range(2,1000001):
  29.     if i/plist[i] > maxnphi:
  30.         maxnphi = i/plist[i]
  31.         maxn = i
  32. print (maxn,maxnphi)
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-1-24 14:38:21 | 显示全部楼层
jerryxjr1220 发表于 2016-10-16 08:17
答案:
510510 5.539388020833333
[Finished in 2.9 sec]

学习 感谢分享
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-10-5 19:33:32 | 显示全部楼层
用的matlab

ans =

      510510

时间已过 0.001139 秒。
>>
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-27 10:33:06 | 显示全部楼层
510510

Process returned 0 (0x0)   execution time : 3.888 s
Press any key to continue.
2#大大的递推思路很硬核,只是我没实现出来……
不论如何涨姿势了
转化为倒数的最小值,利用两个结论预先打部分表
1.p为质数时,有

                               
登录/注册后可看大图

2.正整数m,n互质时,有

                               
登录/注册后可看大图

  1. #include<iostream>
  2. #include<cmath>
  3. #include<set>
  4. #include<algorithm>
  5. using namespace std;

  6. const int M = 1e6;
  7. const int M_RANGE = 1e6;
  8. int ct = 0;
  9. bool prime[M];
  10. int factor[M];
  11. int phi[M] = {0};

  12. void euler_sieve(){
  13.   prime[1] = false;
  14.   for (int i = 2;i <= M;i++) prime[i] = true;

  15.   for (int i = 2;i <= M;i++){
  16.     if (prime[i]) {factor[++ct] = i;  phi[i] = i-1;}
  17.     for (int j = 1;j <= ct && i*factor[j] < M;j++){
  18.       prime[i*factor[j]] = false;
  19.       if (i % factor[j] == 0) break;
  20.     }
  21.   }
  22. }

  23. void ini(){
  24.   for (int i = 2;i <= sqrt(M);i++){
  25.     if (prime[i]){
  26.       for (int j = i;j*i <= M;j*=i){
  27.         phi[j*i] = phi[j]*i;
  28.       }
  29.       for (int j = i;j*i <= M;j++){
  30.         if (prime[j]) phi[j*i] = phi[j]*phi[i];
  31.       }
  32.     }
  33.   }
  34. }

  35. void solve(set<int> & p,int n){
  36.   for (int i = 1;n != 1;i++){
  37.     int t = factor[i];
  38.     while(n % t == 0) {p.insert(t); n /= t;}
  39.   }
  40. }

  41. double quot(const set<int> & p){
  42.   double res = 1;

  43.   for (set<int>::iterator it = p.begin();it != p.end();++it){
  44.     res *= *it - 1;
  45.     res /= *it;
  46.   }
  47.   return res;
  48. }

  49. int main(){
  50.   euler_sieve();
  51.   ini();
  52.   double mn = 1;//min
  53.   int ans;

  54.   for (int i = 2;i <= M;i++){
  55.     set<int> p;
  56.     double t;

  57.     if (phi[i]) t = phi[i] / (double)i;
  58.     else{
  59.       solve(p,i);
  60.       t = quot(p);
  61.     }
  62.     if (t < mn) {mn = t;  ans = i;}
  63.     //cout << i << " " << t << endl;
  64.   }
  65.   cout << ans << endl;
  66.   return 0;
  67. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-27 10:38:34 | 显示全部楼层
补图

                               
登录/注册后可看大图


                               
登录/注册后可看大图
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-2-9 13:42:30 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2021-2-20 20:37 编辑

C++ 12ms
  1. #include<iostream>
  2. #include<vector>
  3. #include<cstring>
  4. using namespace std;



  5. template<size_t size, typename T>
  6. void euler_sieve(bool (&is_prime)[size], vector<T>& primes, T (&phi)[size]) {
  7.     T i, k;
  8.     memset(is_prime, -1, size);
  9.     is_prime[0] = is_prime[1] = 0;

  10.     for (i = 2; i < size; i++) {
  11.         if (is_prime[i]) {
  12.             primes.push_back(i);
  13.             phi[i] = i - 1;
  14.         }

  15.         for (T j : primes) {
  16.             k = i * j;

  17.             if (k >= size) {
  18.                 break;
  19.             }

  20.             is_prime[k] = false;

  21.             if (!(i % j)) {
  22.                 phi[k] = phi[i] * j;
  23.                 break;
  24.             }

  25.             phi[k] = phi[i] * (j - 1);
  26.         }
  27.     }
  28. }



  29. int main() {
  30.     ios::sync_with_stdio(false);

  31.     constexpr unsigned int UPPER_BOUND = 1000000;
  32.     static bool is_prime[UPPER_BOUND];
  33.     static unsigned int phi[UPPER_BOUND];
  34.     vector<unsigned int> primes;
  35.     double max_div = 0, div;
  36.     unsigned int max_n = 0, n;

  37.     euler_sieve(is_prime, primes, phi);


  38.     for (n = 2; n < UPPER_BOUND; n++) {
  39.         div = (double)n / phi[n];

  40.         if (div > max_div) {
  41.             max_div = div;
  42.             max_n = n;
  43.         }
  44.     }


  45.     cout << max_n << endl;
  46.     return 0;
  47. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-3-21 12:07:25 | 显示全部楼层
本帖最后由 guosl 于 2022-1-11 19:18 编辑

我们可以应用筛法来批量求出各数的欧拉函数值。
  1. /*
  2. 答案:510510
  3. 耗时:0.0148415秒
  4. */
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstring>
  8. using namespace std;

  9. const int nN = 1000001;
  10. int f[nN];//记录φ(i)

  11. int main(void)
  12. {
  13.   double d = 0.0;
  14.   int m = 0;
  15.   //计算φ(i)
  16.   for (int i = 1; i < nN; ++i)
  17.   {
  18.     f[i] = i;
  19.     if ((i & 1) == 0)
  20.       f[i] /= 2;
  21.   }
  22.   for (int i = 3; i < nN; i += 2)
  23.   {
  24.     if (f[i] < i)
  25.       continue;
  26.     for (int j = i; j < nN; j += i)
  27.       f[j] = f[j] / i * (i - 1);
  28.   }
  29.   for (int i = 2; i <= 1000000; ++i)
  30.   {
  31.     double td = double(i) / double(f[i]);
  32.     if (td > d)
  33.     {
  34.       m = i;
  35.       d = td;
  36.     }
  37.   }
  38.   cout << m << endl;
  39.   return 0;
  40. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-5-11 15:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表