나머지연산
(a+b) % c = ((a%c) + (b%c)) % c
(a*b) % c = ((a*c) + (b*c)) % c
최대공약수(유클리드 호제법)
GCD(a, b) = GCD(b, a%b) -> a%b가 0일 때 그때의 b값이 최대공약수
|
1
2
3
4
5
6
7
8
9
10
11
12
|
int gcd(int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd(b, a%b);
}
}
|
cs |
* GCD(a, b, c) = GCD(GCD(a, b), c) // 더 많은 N개의 최대공약수를 구하는 것도 같은 방식
최대공배수
LCM(a, b) = (a*b) / (GCD(a, b))