5.Smallest multiple

问题描述

$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from $1$ to $20$?

evenly divisible: divisible with no remainder

解法

数学解法：

题意的意思让你求一个能被$1$ ~ $20$ 都能整除的一个整数。

我们最直接的想法就是去找$1$ ~ $20$ 的最小公倍数。

欧几里得算法求出即可

#include <bits/stdc++.h>
#define ll long long
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;

const int maxn = 20 + 5;
int a[maxn];
int gcd(int a, int b)
{
    if(a % b == 0)
        return b;
    else
        return gcd(b, a%b);
}
int main(void)
{
    IOS
    for(int i = 1; i <= 20; i++)
        a[i] = i;
    int flag = a[1];
    for(int i = 1; i <= 20; i++)
        flag = a[i] / gcd(a[i], flag) * flag;
    printf("%d\n"flag);
    return 0;
}

参考资料可参考:（有关于数论的基本问题）

• https://blog.csdn.net/leimingfu/article/details/97244935

• https://blog.csdn.net/NJU_Flepped/article/details/76270241

我们可以采用暴力的方案得出结果 因为数据量只有20 ，我们可以用对$i$ 和$j$ 遍历寻找一个$i$满足对$1$ ~$20$都满足整除方案。

#include <bits/stdc++.h>
#define ll long long
#define IOS {ios::sync_with_stdio(false);cin.tie(0);}
using namespace std;

int main(void)
{
    IOS
 for(int i = 1; ; i++)
    {
        int flag = 1;
        for(int j =1 ; j <= 20; j++)
     {
            if(i % j != 0)
         {
                flag = 0;
                break;
            }
        }
        //flag的判断放到i循环中
        if(flag == 1)
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}

注意点

1. 在求解最小公倍数的时候,有定理：

   $$x、y 两个数的最小公倍数乘以它们的最大公约数等于 x 和 y 本身的乘积$$

   故存在公式:

   $$LCM(x,y)=x/GCD(x,y)*b$$

   但计算过程中不能写成：

   $$LCM(x,y)=(x*y)/GCD(x,y)$$

   会存在$x * y$的精度溢出。

   打表程序如下:

   #include <bits/stdc++.h>
   #define ll long long
   #define IOS {ios::sync_with_stdio(false);cin.tie(0);}
   using namespace std;
   
   const ll maxn = 20 + 5;
   ll a[maxn];
   ll gcd(ll a, ll b)
   {
       if(a % b == 0)
           return b;
       else
           return gcd(b, a%b);
   }
   int main(void)
   {
       IOS
       for(ll i = 1; i <= 20; i++)
           a[i] = i;
       ll flag1 = a[1];
       ll flag2 = a[1];
       for(ll i = 1; i <= 20; i++)
       {
           flag1 = (a[i] * flag1) / (gcd(a[i], flag1));
           cout << "#对flag1" << "-----" << i << "####" << flag1 << endl;
       }
       cout << endl << endl;
       for(ll i = 1; i <= 20; i++)
       {
           flag2 = a[i] / gcd(a[i], flag2) * flag2;
           cout << "#对flag2" << "-----" << i << "####" << flag2 << endl;
       }
       printf("%lld\n%lld\n",flag1, flag2);
       return 0;
   }

   我吐了….

   最后出现了精度溢出…

   在 $flag * 20$的时候……

   

正确答案

$$Answer: 232792560$$

官方解答