项目欧拉#5;这个解决方案有效 - 但为什么?

dab 发布于 2019-07-12 algorithm 最后更新 2019-07-12 09:32 1 浏览

项目欧拉问题5表述为:“2520是可以由1到10中的每个数除以而不剩余的最小数。 从1到20的所有数字均匀分布的最小正数是多少?“ 以下是我正在使用的函数的c ++代码。

    long long unsigned int rangeLCM(int n)
    {
         long long unsigned int ans=1;
         for(int i=1;i<=n;i++)
         {
            if(ans%i!=0)
            {
              if(i%(ans%i)==0)ans*=(i/(ans%i));
              else ans*=i;
            }
         } 
         return ans;
    }
该代码适用于问题中提出的示例以及问题本身{rangeLCM(10)=2520rangeLCM(20)=232792560},但我认为这并不完美,并且在某些边缘案例中错过了。 我没有真正计算LCM(ans,i),而是检查了两个中的较大者(总是ans)可被i整除。如果不是,则ans乘以等于i/(ans%i)i的数字,取决于i是否可被(ans%i)整除。 这是基于以下事实:
LCM(8,12)=24=12*(8/(12%8));
LCM(9,30)=90=30*(9/(30%9)
LCM(7,13)=91=13*7
但是,对于以下类型的案例,它失败:LCM(8,14)=56 != 8*14 然而,rangeLCM的代码为我尝试过的所有输入提供了正确的输出。为什么?
已邀请:

lmagni

赞同来自:

你的逻辑不起作用

          if(i%(ans%i)==0)ans*=(i/(ans%i));
          else ans*=i;
例如,如果ans = 10i = 14,那么,lcm应该是70,但在你的代码中,它是140。 原因是,在ansi之间,存在公约数,但是您的代码无法检测到它。 为了实验,我编写了一小段代码来检查使用Java。
class Solution {
public static void main(String[] args) {
        long ans = 1;
        for (long i = 1; i <= 40; i++) {
            if (ans % i != 0) {
long before = (ans*i/gcd(ans,i));
                if (i % (ans % i) == 0){
                    ans *= (i / (ans % i));
                }else{
                    ans *= i;
                }
                System.out.println(ans + " " + before + " " + i);
            }
        }
    }
public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}
产量
2 2 2
6 6 3
12 12 4
60 60 5
420 420 7
840 840 8
2520 2520 9
27720 27720 11
360360 360360 13
720720 720720 16
12252240 12252240 17
232792560 232792560 19
5354228880 5354228880 23
26771144400 26771144400 25
722820898800 80313433200 27
20961806065200 20961806065200 29
649815988021200 649815988021200 31
1299631976042400 1299631976042400 32
48086383113568800 48086383113568800 37
当i = 27时,正确答案与ans之间存在差异 lcm(a,b)的公式是
lcm(a,b) = a*b/gcd(a,b)
gcd是两个数字a和b之间的Greatest common divisor

eet

赞同来自:

我认为你错过了很多你需要实现欧几里德算法的情况

if(i%(ans%i)==0)ans*=(i/(ans%i));