수학

수학

1. 나머지연산 

정답을 구할때 너무크면 나머지로 출력하는문제많음.

최종에서하지말고

매번나머지해도됨

나머지연산은 덧셈곱셈에 닫혀있고, 뺄셈도있긴한데 다름

나누기연산은 안됨 (6/3)%3 이 그 예

10403문제

빼기예제 (6-5)%3 = 1

파이썬에서는 1나오는데

C++ 이나 java는 -2가 나옴

그래서 각자나머지한거에서 나누는수 한번 더 해주면 성립

페르마의소정리

(a/b) %c

 = (a x b^(c-2) ) % c

 (단 c는 소수, a 와 b는 서로소)

2. 최대공약수

정답이 분수형태일때 기약분수 나타낼때

GCD

int g = 1;

for(int i = 2; i<=min(a,b) ; i++){

if(a%i == 0 && b % i ==0 ) {

g = i ;

}

}

시간복잡도 O(N)

유클리드 호제법이 더좋음

 GCD(a,b) = GCD(b,a%b)

재귀쓸때

int gcd(int a, int b){

if(b==0){

return a;

 } else{

return gcd(b,a%b);

}

}

유클리드호제법 시간복잡도 O(log N)

 안쓸대

int gcd(int a, int b) {

while(b!=0){

int r = a%b;

a =b;

b =r;

}

return a;

}

이것도 시간복잡도 O(log N)

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

최소공배수

3. 소수

약수가 1이랑 자기자신

1) 어떤수가 소수이닌지 판별

2보다크고 N보다작은것들로 나눠

2보다크고 N/2보다 작은것들로 나눠

2보다크고 루트N보다 작은것들로 나눠 O(루트N)

2) N보다 작거나 같은 소수 찾아내기( N까지수를 루트N으로 조지니까 O(N루트N)

에라토스테네스의 체

2~100까지는 2 3 5 7 로 인해서 다지워짐  

int prime[100];

int pn = 0;

bool check[101] ;

int n = 100;

for(int i = 2;  i<=n ; i ++){

if(check[i] == false){

prime[pn++]=i;

for(int jk =i*i; j<=n; j+=i){

check[j] = true;

}

}

}

이미검사한 영역에대해서 당겨서 검사하는거 중요

시간복잡도 O(Nlog(logN))

골드바흐의 추측

2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.

위문장에 3을 더하면

5보다 큰 모든 홀수는 세소수의 합으로 표현 가능하다

진짜 추측임 10의 18승 이하에서는 참인것이 증명됨

결국 에라토스 체에서 false로 그 배열 자리에 소수인놈 저장해놨으니

수가 크면 한쪽소수 정해놓고 p+q = N 이런식으로해서 p 정해보고

 N-p가 false인지 체크해보면됨