#1 Number theory, Simple math

소수

1. 모든 자연수는 소인수들의 곱으로 표현 가능

2. 소수는 무한하다 (p1 * p2 * p3 ....* pn + 1)

 

소수인지 알아보는 방법

 

n이 합성수라고 가정하면, a * b = n 을 만족하는 (min(a,b) > 1) 인 (a, b)가 존재하므로 min(a, b) <= √n 을 만족

bool pr(ll x) {
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0)return false; //x가 i로 나누어 떨어지면 합성수
    return true;
}
 

 

에라토스테네스의 체를 이용 시간 복잡도 : (O(nloglogn))  / 공간 복잡도 : O(n)

앞에서 부터 소수의 배수가 되는 수들을 전부 지워 가가는 것

ll sieve[101010];
bool init(){
    for(ll i = 2; i < 101010; i++){
       if(sieve[i]) continue;
       //sieve[i]가 0이 아니면 합성수
       for(ll j = i + i; j < 101010; j += i) sieve[j] = 1;
}
 

 

최대공약수를 구해주는 유클리드 알고리즘

ll gcd(ll x, ll y) {
    if (!y) return x;
    return gcd(y, x % y);
}

gcd(a, b)를 구하는 과정에서 max(a, b)가 절반이하가 되므로 시간복잡도는 O(log n)

" 문제 크기가 절반 이하가 되기 때문에 O(log n)이 보장된다."

 

최대 공약수 특징

gcd(a, b) = gcd(a + cb, b) 입니다.

 

확장 유클리드 알고리즘(Extended Euclidean)

a, b, c 가 상수로 주어졌을때, ax + by = c를 만족하는 두 정수 x와 y를 구하는 알고리즘

1) c가 gcd(a, b)의 배수가 아니면 해가 존재하지않는다.

2) c가 gcd(a, b)의 배수면 항상 해가 존재한다.

c가 gcd(a, b)의 배수라면 x와 y를 c/gcd(a, b)배 해주면 되기 때문에 

ax + by = c 와 ax + by = gcd(a, b)는 동치이다

(ax + by = gcd(a, b)의 해가 나오면 거기서 c /gcd(a, b)를 곱해주면 ax + by = c의 해가 나오기 때문)

 

ex) 26x + 8y = gcd(26, 8)

26x + 8y

26 = 8 * 3 + 2

8 = 2 * 4 + 0

gcd(26, 8) = 2

	x	y	r	q
i = 0	1	0	26
i = 1	0	1	8	3 (26 / 8)
i = 2	1 (-3 * 0)	-3 (-3 * 1)	2 (26 - 8 * 3)	4 (8 / 2)
i = 3			0

i=0, 1 에서 x=1, y=0, x=0, y=1을 넣고 초기화 시킵니다.

r이 0이 될때 그 전의 x와 y가 해가 됩니다. 따라서 x = 1, y = -3이 됩니다.

26 * 1 + 8 * (-3) = 2

 

집합 S = {ma + nb | m, n ∈ 정수, ma + nb > 0} 인 집합 S의 최소원소는 gcd(a, b)

S는 공집합이 아니고 S는 자연수 집합이므로 최소원소가 존재

#include<iostream>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll ex_gcd(ll a, ll b, ll& x, ll& y);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    
    ll xx, yy;
    ll ggc = ex_gcd(26, 8, xx,yy);
    cout << ggc <<' '<< xx <<' '<< yy;
 
    return 0;
}
ll ex_gcd(ll a, ll b, ll& x, ll& y) { //gcd(a, b)를 return 
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll ret = ex_gcd(b, a % b, x, y);
    ll temp = y;
    y = x - (a / b) * y;
    x = temp;
    if (x <= 0) { //x를 양수로 만들어주는 작업 또는 오버플로우 방지
        x += b;
        y -= a;
    }
    return ret;
}
 
 
 

함수의 인자로 x와 y를 &(reference)로 받은 이유는 아직 x와 y를 모르고 있기 때문입니다. 

함수가 돌아가면서 x와 y의 값을 결정하게 해줍니다. 

 

Congruences (합동)

"a와 b가 법m 으로 합동이다" 라는 의미는 a와 b를 m으로 나눈 나머지가 같다는 의미

기호로 a ≡ b (mod m) 으로 나타낸다. 

ax ≡ 1 (mod m) 을 만족하는 x를 a의 modulo inverse(모듈로 역원) 라고 하고 유일하다.

(오버 플로우 방지 등)

m이 소수면 a^m-2 가 modulo inverse 이다.

ex) a=2, m=5 => 2 * 2^(5-2) mod 5 => 16 mod 5 =1 = (1 mod 5)

분할정복을 이용한 거듭제곱을 통해 O(log m)의 시간복잡도에 구할 수 있다.

m이 소수가 아닐때는 확장 유클리드 알고리즘을 이용한다.

ax ≡ 1 이라는 것은 ax + my = 1을 만족하는 것과 동치이므로 확장 유클리드를 이용해서 x와 y를 구해준다.

여기서 곱셈의 역원이 존재한다는 의미는 a와 m이 서로소이여야만 역원을 찾을 수 있다.

 

Harmonic sequence (조화 수열)

1/1 + 1/2 + 1/3 + 1/4 + .....1/n = O(log n)

위의 사실을 이용하면 여러 문제들의 시간복잡도를 분석할 수 있다.

a(i) = [n/i] 로 정의 하면 ( [n/i]는 n을 i로 나눴을때 정부부분 ,즉 몫)

n = 10 일때 (i는 1부터 시작) a(i) = 10, 5, 3, 2, 2, 1, 1, 1, 1

수열 a(i)의 서로 다른 값은 2√n 개 이하이다. 

이를 이용하여 O(√n) 동안 a(i)의 모든 값을 전부 다 확인할 수 있다. 따라서 몫의 합도 알 수 있다.

#include<iostream>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    ll sum = 0;
    ll n;
    cin >> n;
    for (ll i = 1, j; i <= n; i = j + 1) {
        j = n / (n / i); //같은 값을 가지는 최대원소
        sum += (n / i) * (j - i + 1);
        cout << j << ' ' << sum << '\n';
    }
    
 
    return 0;
}
 
 
 

1	2	3	4	5	6	7	8	9	10
10	5	3	2	2	1	1	1	1	1

변수 j는 수열 a(i)의 같은 값중에 가장 큰 원소를 가집니다.

따라서 j는 1, 2, 3, 5, 10 값을 가집니다.

sum은 수열 a(i)의 모든 합입니다.