4. 정수론-소인수분해, gcd, lcm, sieve

4.md

0.01MB

0. 복습

1. mod n

• 덧셈

7 = 3 (mod 4)

ex) a+b = (a+b)%n (mod n)

7 + 9 = 16 = 0 (mod 4)

3 + 1 = 4 = 0 (mod 4)

12312312 + 234234234 = 0 + 2 = 2 (mod 4)

• 곱셈

7*9 = 63 = 3 (mod 4)

3 * 1 = 3 (mod 4)

즉, 미리 mod를 적용해주면 식이 간단해진다.

답이 심각하게 커지는 경우, mod를 많이 쓰며 나중에 다이나믹 프로그래밍에서 많이 나온다.

참고 문제 : [boj.kr/17466]

2. 소인수 분해

어떤 수를 소인수 분해 하려면, 2부터 sqrt(N)까지 원소들의 조건을 따지면서 분해하면 된다.

(1) N이 합성수인 경우, N = p1^r1 * p2^r2 * p3^r3 * ... * pk^rk

N = 2^r1 * 3^r2 * 5^r3 * p4^r4

• 어떤 N이 오직 sqrt(N)보다 작은 소인수로 이루어짐

이때는 자명하므로 패스.

• 어떤 N을 소인수 분해했을 때 sqrt(N)보다 큰 소인수도 있음

sqrt(N)보다 큰 소인수는 지수가 무조건 1이다. (하나밖에 없다) => 지수가 2개 이상이면 그 2개만으로 N을 넘어버리기 때문에 1개밖에 없다.

(2) N이 소수인 경우, 어떤 N을 소인수 분해했을 때 sqrt(N)보다 큰 소인수도 있다는 조건과 같음. 따라서 예외처리할 필요 없음.

#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int> > v;
int main(){
    int N; cin >> N;
    for(int p=2; p*p<=N; ++p){
        int cnt=0;
        while(N%p==0){
            N/=p;
            cnt++;
        }
        if(cnt!=0) v.push_back(make_pair(p, cnt));
    }
    if(N != 1) {
        v.push_back(make_pair(N, 1));
    }
    cout << "N의 소인수분해" << '\n';
    for(int i=0; i<v.size(); ++i){
        cout << v[i].first << '^' << v[i].second << '\n';
    }
}

참고 문제 : [boj.kr/7806, boj.kr/2312]

3. 최대공약수 gcd(greatest common divisor)

최대공약수를 소인수 분해를 이용해서 하면, 시간이 매우 오래걸린다.

따라서 유클리드 호제법을 쓴다.

gcd(35, 25) = gcd(25, 10) = gcd(10, 15) = gcd(15, 10) = gcd(10, 5) = gcd(5, 5) = gcd(5,0) = 5.

이걸 살짝 변형해서 현대에는

gcd(35, 25) = gcd(25, 10) = gcd(10, 5) = gcd(5, 0) = 5.

식 : gcd(a, b) = gcd(b, a%b)이고, gcd(k, 0)일 때 답은 k ( 단, a, b, k가 양의 정수일 때)

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

재귀함수로 구현 가능하다.

팁1 : 시간복잡도는 최악 O(log_10(N))이다. 하지만 정말 빠르기 때문에 O(1)이라고 과장해서 말할 수도 있다.

팁2 : a가 b보다 작아도 예외처리 안해도 된다.

4. 최소공배수 lcm(least common multiple)

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

long long lcm(int a, int b) {
  return a/gcd(a, b) * b;
}

팁1 : 오버플로우 조심해야한다.

팁2 : b/gcd(a,b) * a해도 동일하게 나온다.

참고 문제 : [boj.kr/2609, boj.kr/9613, boj.kr/1735]

5. 에라토스테네스의 체(sieve)

소수 구하는 알고리즘. 2부터 sqrt(N)까지 i*i ~ N 구간 내에 있는 i의 모든 배수를 지운다. 끝나고 남은 숫자들이 모두 소수.

#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 1e6; // 백만
bool isErased[MAX_N+1];
// sieve[p] == false : p가 아직 안지워졌다.
// sieve[p] == true  : p가 지워졌다.
int main(){
    int N; cin >> N;

    isErased[0] = true;
    isErased[1] = true;
    for(int p=2; p*p <=N; ++p){
        if(isErased[p]) continue;
        for(int j=p*p; j<=N; j+=p){
            isErased[j]=true;
        }
    }
    while(true){
        int K; cin >> K;
        if(isErased[K]) cout << "소수 아님" << '\n';
        else cout << "소수!" << '\n';
    }
}

시간 복잡도는 O(N * log(log N)). 사실상 O(N)

참고 문제 : [boj.kr/1978, boj.kr/1929, boj.kr/4948, boj.kr/1456, boj.kr/1676, boj.kr/2004]

99. 부록 : 참고 문제 풀이

• boj.kr/17466

#include <iostream>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N, P; cin >> N >> P;
    int res = 1;
    for(int i=1; i<=N; ++i){
        res = (res * (long long)i) % P;


    }
    cout << res << '\n';
}

• boj.kr/7806

#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int> > v;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;
    for(int p=2; p*p<=N; ++p){
        int cnt=0;
        while(N%p==0){
            N/=p;
            cnt++;
        }
        if(cnt!=0) v.push_back(make_pair(p, cnt));
    }
    if(N != 1) {
        v.push_back(make_pair(N, 1));
    }
    for(int i=0; i<v.size(); ++i){
        for(int j=0; j<v[i].second; ++j){
            cout << v[i].first << '\n';
        }
    }
}

• boj.kr/2312

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int T; cin >> T;
    while(T--){
        vector<pair<int, int> > v;
        int N; cin >> N;
        for(int p=2; p*p<=N; ++p){
            int cnt=0;
            while(N%p==0){
                N/=p;
                cnt++;
            }
            if(cnt!=0) v.push_back(make_pair(p, cnt));
        }
        if(N != 1) {
            v.push_back(make_pair(N, 1));
        }
        for(int i=0; i<v.size(); ++i){
            cout << v[i].first << ' ' << v[i].second << '\n';
        }
    }
}

• boj.kr/2609

#include <iostream>
using namespace std;
int gcd(int a, int b){
    if(!b) return a;
    return gcd(b, a%b);
}
long long lcm(int a, int b){
    return a/gcd(a, b) * b;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int a, b; cin >> a >> b;
    cout << gcd(a,b) << '\n' << lcm(a,b) << '\n';
}

• boj.kr/9613

#include <iostream>
using namespace std;
typedef long long int ll;
ll gcd(int a, int b){
    if(b==0) return a;
    return gcd(b, a%b);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t; cin >> t;
    while(t--){
        ll n; cin >> n;
        ll arr[101];
        for(int i=0; i<n; ++i){
            cin >> arr[i];
        }
        ll res=0;
        for(int i=0; i<n-1; ++i){
            for(int j=i+1; j<n; ++j){
                res+=gcd(arr[i], arr[j]);
            }
        }
        cout << res << '\n';
    }
}

• boj.kr/1735

#include <iostream>
using namespace std;
int gcd(int a, int b){
    if(!b) return a;
    return gcd(b, a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b) * b;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int a, b, c, d; cin >> a >> b >> c >> d;
    int mo = lcm(b, d);
    int ja = lcm(b, d)/d*c + lcm(b,d)/b*a;

    cout << ja/gcd(mo, ja) << ' ' << mo/gcd(mo, ja) << '\n';
}

• boj.kr/1978

#include <iostream>
using namespace std;
const int MAX_N = 1001;
bool isErased[MAX_N+1];

int main(){
    ios_base::sync_with_stdio(false); cin.tie();

    isErased[0] = true;
    isErased[1] = true;
    for(int p=2; p*p <=1000; ++p){
        if(isErased[p]) continue;
        for(int j=p*p; j<=1000; j+=p){
            isErased[j]=true;
        }
    }

    int N; cin >> N;
    int cnt=0;
    while(N--){
        int a; cin >> a;
        if(!isErased[a]) cnt++;
    }

    cout << cnt << '\n';
}

• boj.kr/1929

#include <iostream>
using namespace std;
const int MAX_N = 1000001;
bool isErased[MAX_N+1];

int main(){
    ios_base::sync_with_stdio(false); cin.tie();

    isErased[0] = true;
    isErased[1] = true;
    for(int p=2; p*p <=MAX_N; ++p){
        if(isErased[p]) continue;
        for(int j=p*p; j<=MAX_N; j+=p){
            isErased[j]=true;
        }
    }
    int a, b; cin >> a >> b;
    for(int i=a; i<=b; ++i){
        if(!isErased[i]) cout << i << '\n';
    }
}

• boj.kr/4948

#include <iostream>
using namespace std;
const int MAX_N = 247000;
bool isErased[MAX_N+1];

int main(){
    ios_base::sync_with_stdio(false); cin.tie();

    isErased[0] = true;
    isErased[1] = true;
    for(int p=2; p*p <=MAX_N; ++p){
        if(isErased[p]) continue;
        for(int j=p*p; j<=MAX_N; j+=p){
            isErased[j]=true;
        }
    }
    while(1){
        int a, cnt=0; cin >> a;
        if(a==0) break;
        for(int i=a+1; i<=2*a; ++i){
            if(!isErased[i]) cnt++;
        }
        cout << cnt << '\n';
    }
}

• boj.kr/1456 ( long long 범위 벗어나는거 조심)

#include <iostream>
#include <cmath>
typedef long long ll;
using namespace std;
const int MAX_N = 1e7;
bool isErased[MAX_N+1];
int main(){
    ll a, b;
    cin >> a >> b;
    isErased[0] = true;
    isErased[1] = true;
    for(ll p=2; p<=MAX_N; ++p){
        if(isErased[p]) continue;
        for(ll j=p*p; j<=MAX_N; j=j+p){
            isErased[j]=true;
        }
    }
    ll cnt = 0;
    ll aa = sqrt(a);
    for(ll p=2; p*p<=b; p=p+1){
        if(!isErased[p]) {
            for(ll k=p; p<=b/k; k=k*p){
                if(k*p>=a) cnt = cnt + 1;
            }
        }
    }
    cout << cnt << '\n';
}

• boj.kr/1676

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N;
    cin >> N;
    int k=2;
    int cnt2=0, cnt5=0;
    while(k<=N){
        cnt2+=N/k;
        k*=2;
    }
    k=5;
    while(k<=N){
        cnt5+=N/k;
        k*=5;
    }
    cout << min(cnt2, cnt5) << '\n';
}

• boj.kr/2004

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll cnt2=0, cnt5=0;
void f(ll N){
    ll k=2;
    while(k<=N){
        cnt2+=N/k;
        k*=2;
    }
    k=5;
    while(k<=N){
        cnt5+=N/k;
        k*=5;
    }
}
void f2(ll N1, ll N2){
    ll k=2;
    while(k<=N1){
        cnt2-=N1/k;
        k*=2;
    }
    k=2;
    while(k<=N2){
        cnt2-=N2/k;
        k*=2;
    }
    k=5;
    while(k<=N1){
        cnt5-=N1/k;
        k*=5;
    }
    k=5;
    while(k<=N2){
        cnt5-=N2/k;
        k*=5;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n, m;
    cin >> n >> m;

    f(n);
    f2(m, n-m);
    if(min(cnt2, cnt5)<=0){
        cout << '0' << '\n';
    }
    else {
        cout << min(cnt2, cnt5) << '\n';
    }
}