CF1717A题解

标签：frac gcd int 题解 times text CF1717A

题目

\[\text{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)} \]

\[\frac{\text{lcm}(a,b)}{\gcd(a,b)}=\frac{a}{\gcd(a,b)}\times\frac{b}{\gcd(a,b)} \]

\[\frac{a}{\gcd(a,b)}\times\frac{b}{\gcd(a,b)}\leq 3 \]

\[\frac{a}{\gcd(a,b)}\times\frac{b}{\gcd(a,b)} \text{是整数，只可能是}1,2,3\text{。} \]

\[b\text{是}a\text{的}1\text{倍}2\text{倍}\text{或}3\text{倍。} \]

\[a\text{是}b\text{的}1\text{倍}2\text{倍}\text{或}3\text{倍。} \]

\[ans=(a=b\text{的情况})+((a=2b\text{的情况})+(a=3b\text{的情况}))\times2 \]

\[ans=n+(n/2+n/3)\times2 \]

代码

#include<cstdio>
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%d\n",n+(n/2+n/3)*2);
    }
    return 0;
}

洛谷通过不了QwQ

标签：frac,gcd,int,题解,times,text,CF1717A
From： https://www.cnblogs.com/maniubi/p/16660587.html