GCD and LCM

Rewind my little memories of number thoery..

---

GCD和辗转相除法(Euclidean Algorithm)

int gcd(int a,int b){
  return b?gcd(b,a%b):a;
}

Idea: old divisor $\div$ old remainder, until we have new remainder=0.

Proof: suppose $a=b+c$ where $a>b$, and $x=gcd(a,b)$.

$\Rightarrow x$ is the divisor of both $a,b$.

$\Rightarrow \frac ax = \frac bx + \frac cx$

$\Rightarrow x=gcd(b,c)$. Otherwise, suppose we have a greater divisor $y=gcd(b,c), y>x$, we will have $\frac by+\frac cy=\frac{b+c}y=\frac ay=an\ integer$. This is a contradiction to the assumption that $x=gcd(a,b)$

Now we can continue to let $b=c+d,x=gcd(c,d)$ until $d=0$, and $x$ is the last non-zero number.

We replace the repeated subtractions by divisions and know the algorithm is correct.

LCM

lcm=a*b/gcd(a,b)

Idea: $a*b=lcm(a,b)*gcd(a,b)$

Proof: Think of prime factorization, $gcd(a,b)=prime(a)\cap prime(b)$, and $lcm(a,b)=prime(a)\cup prime(b)$. So multiply these two will have every prime of $a,b$ with exact times.

C++17

都是老黄历了，C++17已经增加了std::gcd()和std::lcm()，不用自己写了。

Simple Exercise

Codeforces 858A

The k-rounding number ends with k zeros and is divisble by n. So $10^k$ and n are divisor of this number. K-rounding = $lcm(n,10^k)$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
const int INF = 1e9;
const int N = 100;
 
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
 
int main(){
    ll n,k;
    cin>>n>>k;
    ll z=1;
    while(k--)z*=10;
    ll ans=n*(z/gcd(n,z));
    cout<<ans;
    return 0;
}