【欧拉计划】5. Smallest multiple

（本题取 $n=20$）

【思路】本题只需求 $1 \sim 20$ 的最小公倍数即可。

而 $\text{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}$，因此问题转化成了求 $\gcd$（为了防止爆 int 可以先除后乘或者直接开 long long）。时间复杂度为 $\mathcal O(\log n)$：

#include<stdio.h>
int ans=1;
int gcd(int a,int b)
{
    while(b)
    {
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int main()
{
    for(int i=1;i<=20;++i)ans=lcm(ans,i);
    printf("%d",ans);
    return 0;
}