페르마의 소정리
\(p\)가 소수이고, \(\gcd(p, a) = 1\)일 때
$$a^{p-1} \equiv 1 \mod p$$
앞선 글에서 모듈러 역원을 구하는데 확장 유클리드 알고리즘을 이용할 수 있다는 사실을 알았습니다.
그런데 모듈러가 소수라면, 조금 더 간단하게 모듈러 역원을 구할 수 있습니다.
페르마의 소정리에 따르면, \(p\)가 소수일 때 \(p\)와 서로소인 임의의 \(a\)의 모듈러 역원은 \(a^{p-2}\)입니다.
11401번: 이항 계수 3
자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const ll MOD = 1e9 + 7; // 소수
ll n, k;
ll mpow(ll a, ll n) // a^n O(log n)
{
if (n == 0) return 1;
ll res = mpow(a, n / 2);
res = res * res % MOD;
if (n % 2) res = res * a % MOD;
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
ll res = 1;
for (ll i = 1; i <= n; i++) res = (res * i) % MOD;
for (ll i = 1; i <= k; i++) res = (res * mpow(i, MOD - 2)) % MOD; // i의 모듈러 역원은 i^(MOD - 2)
for (ll i = 1; i <= n - k; i++) res = (res * mpow(i, MOD - 2)) % MOD;
cout << res;
}
|
뤼카의 정리
음이 아닌 정수 \(n, r\)과 소수 \(p\)에 대해,
$$\binom n r \equiv \prod_{i=0}^k \binom {n_i} {r_i} \pmod p$$
\(n\)개 중에 \(r\)개를 고르는 조합의 수를 \(p\)로 나눈 나머지를 구하려고 합니다.
\(n\)이 너무 크면 지금까지 알고있던 방법으로는 빠르게 구할 수 없는데, 뤼카의 정리로 이를 해결할 수 있습니다.
\(n\)과 \(r\)을 각각 \(p\)진법으로 나타내어 봅시다.
\(n = n_kp^k+n_{k-1}p^{k-1}+\cdots+n_1p+n_0\)
\(r = r_kp^k+r_{k-1}p^{k-1}+\cdots+r_1p+r_0\)
\(0 \le i \le k\)에 대해, \(n_i\)에서 \(r_i\)개를 고르는 조합의 수를 모두 곱하면 우리가 구하는 값이 됩니다.
11402번: 이항 계수 4
첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수)
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll n, k, m;
ll mpow(ll a, ll n) // a^n O(log n)
{
if (n == 0) return 1;
ll res = mpow(a, n / 2);
res = res * res % m;
if (n % 2) res = res * a % m;
return res;
}
ll ncr(ll n, ll r) // nCr
{
if (n < r) return 0;
ll res = 1;
for (ll i = 1; i <= n; i++) res = (res * i) % m;
for (ll i = 1; i <= r; i++) res = (res * mpow(i, m - 2)) % m;
for (ll i = 1; i <= n - r; i++) res = (res * mpow(i, m - 2)) % m;
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k >> m;
vector <int> N, K;
while (n || k)
{
N.push_back(n % m);
K.push_back(k % m);
n /= m, k /= m;
}
ll res = 1;
for (int i = 0; i < N.size(); i++)
{
res *= ncr(N[i], K[i]);
res %= m;
}
cout << res;
}
|
중국인의 나머지 정리
모든 \(i \ne j\)에 대하여 \(\gcd(m_i, m_j) = 1\)일 때,
$$\begin{cases} x \equiv n_1 \pmod {m_1} \\ x \equiv n_2 \pmod {m_2} \\ \vdots \\ x \equiv n_k \pmod {m_k} \end{cases}$$
의 해는
$$x\equiv \sum_{i=1}^k M_i(M_i^{-1}\mod{m_i})n_i \pmod{M}$$
입니다. \((M = \prod_i^k {m_i} \), \(M_i = \frac{M}{m_i})\)
모듈러들이 서로 서로소가 아닌 경우에는 모듈러를 소인수 분해해서 각 소인수에 대한 항등식을 따로따로 만들면 됩니다.
15718번: 돌아온 떡파이어
각 테스트 케이스마다 한 줄에 하나씩 나이를 먹는 방법의 가짓 수를 100007로 나눈 나머지를 출력하시오. 100007은 일반적이지 않은 나눗수임에 유의하라.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll mpow(ll a, ll n, ll m) // a^n O(log n)
{
if (n == 0) return 1;
ll res = mpow(a, n / 2, m);
res = res * res % m;
if (n % 2) res = res * a % m;
return res;
}
ll ncr(ll n, ll r, ll m) // nCr
{
if (n < r) return 0;
ll res = 1;
for (ll i = 1; i <= n; i++) res = (res * i) % m;
for (ll i = 1; i <= r; i++) res = (res * mpow(i, m - 2, m)) % m;
for (ll i = 1; i <= n - r; i++) res = (res * mpow(i, m - 2, m)) % m;
return res;
}
ll lucas(ll n, ll r, ll m) // 뤼카의 정리, nCr % m
{
if (r < 0) return 0;
vector <int> N, R;
while (n || r)
{
N.push_back(n % m);
R.push_back(r % m);
n /= m, r /= m;
}
ll res = 1;
for (int i = 0; i < N.size(); i++)
{
res *= ncr(N[i], R[i], m);
res %= m;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
ll n, m; cin >> n >> m;
if (n == 0 && m == 1)
{
cout << "1\n";
continue;
}
// m-1Hn-m+1 = n-1Cn-m+1
// 100007 = 97 * 1031
ll a1 = lucas(n - 1, n - m + 1, 97);
ll a2 = lucas(n - 1, n - m + 1, 1031);
// x = a1 mod 97
// x = a2 mod 1031
// 중국인의 나머지 정리로 100007로 나누었을 때의 나머지를 구한다
ll res1 = 1031 * mpow(1031, 97 - 2, 97) * a1;
ll res2 = 97 * mpow(97, 1031 - 2, 1031) * a2;
cout << (res1 + res2) % 100007 << '\n';
}
}
|
제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.
ANZ1217
무슨 내용을 넣어야 좋을까요?
www.acmicpc.net
'알고리즘 > 수학' 카테고리의 다른 글
| FFT (1) | 2021.03.14 |
|---|---|
| 스프라그–그런디 정리 (1) | 2021.03.13 |
| 기초 정수론1 (0) | 2021.03.11 |