수학

1.나머지 연산

(a+b)%c=((a%c)+(b%c))%c

(a*b)%c=((a%c)*(b%c))%c

(a-b)%c=((a%c)-(b%c)+c)%c  → 뺼셈의 경우 음수가 될 수 있기에 +c를 해줘야한다.

나누기 연산은 불가능

증명) 

a=q1c+r1            a+b=(q1+q2)c+(r1+r2)    →  (a+b)%c =(r1+r2)%c

b=q2c+r2                a%c=r1

                              b%c=r2

                          →a%c+b%c    =r1+r2 이고 여기서 c를 나누면

                                  (r1+r2)%c 이다

2.최대공약수(GCD)

유클리드 호제법

a를 b로 나눈 나머지를 r일떄

GCD(a,b)=GCD(b,r) 이다

재귀함수를 이용한 유클리드 호제법

int gcd(int a,int b){
	if(b==0){
    	return 0;
    }else{
    	return gcd(b,a%b);
        }
    }

 

재귀함수를 사용하지 않고 구현한 유클리드 호제법

int gcd(int a,intb){
	while(b!=0){
    	int r=a%b;
        a=b;
        b=r;
    }
    return 0;
    }

세 수의 최대공약수

GCD(a,b,c)=GCD(GCD(a,b),c)

3.최소 공배수(LCM)

a,b의 최대공약수 g ,최소공배수 l 일떄

l=(a/g)*(b/g)*g