题解 AT4164 【[ABC102A] Multiple of 2 and N】

rui_er

2020-02-13 11:42:18

Solution

题意:求输入的数和 $2$ 的 $\text{lcm}$ 这里根据数学证明可得:$lcm(a, b)=a/\gcd(a, b)*b$,而 $\gcd$ 可以通过辗转相除法计算。以下给出 $\text{Python3}$ 和 $\text{C++}$ 的程序以及伪代码。 Python3: ```py def gcd(x, y): if y == 0: return x return gcd(y, x%y) def lcm(x, y): if x < y: z = x x = y y = z return x / gcd(x, y) * y print(int(lcm(int(input()), 2))) ``` C++: ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; cout<<n/__gcd(max(2, n), min(2, n))*2<<endl; return 0; } ``` 伪代码: ``` int gcd(x, y): if y==0: return x return gcd(y, x mod y) int lcm(x, y): if x < y: swap x ↔ y return x/gcd(x, y)*y input n print lcm(n, 2) ```