1/*
2 * μ μλ‘ (Number Theory)
3 * GCD/LCM, Prime, Modular Arithmetic, Combinatorics
4 *
5 * μνμ λ¬Έμ ν΄κ²°μ μν μκ³ λ¦¬μ¦μ
λλ€.
6 */
7
8#include <iostream>
9#include <vector>
10#include <cmath>
11#include <algorithm>
12#include <numeric>
13
14using namespace std;
15
16const long long MOD = 1e9 + 7;
17
18// =============================================================================
19// 1. GCD / LCM
20// =============================================================================
21
22long long gcd(long long a, long long b) {
23 while (b) {
24 a %= b;
25 swap(a, b);
26 }
27 return a;
28}
29
30long long lcm(long long a, long long b) {
31 return a / gcd(a, b) * b;
32}
33
34// νμ₯ μ ν΄λ¦¬λ μκ³ λ¦¬μ¦
35// ax + by = gcd(a, b)λ₯Ό λ§μ‘±νλ x, y λ°ν
36tuple<long long, long long, long long> extendedGcd(long long a, long long b) {
37 if (b == 0) {
38 return {a, 1, 0};
39 }
40 auto [g, x1, y1] = extendedGcd(b, a % b);
41 return {g, y1, x1 - (a / b) * y1};
42}
43
44// =============================================================================
45// 2. μμ νμ λ° μμ±
46// =============================================================================
47
48bool isPrime(long long n) {
49 if (n < 2) return false;
50 if (n == 2) return true;
51 if (n % 2 == 0) return false;
52
53 for (long long i = 3; i * i <= n; i += 2) {
54 if (n % i == 0) return false;
55 }
56 return true;
57}
58
59// μλΌν μ€ν
λ€μ€μ 체
60vector<bool> sieveOfEratosthenes(int n) {
61 vector<bool> isPrime(n + 1, true);
62 isPrime[0] = isPrime[1] = false;
63
64 for (int i = 2; i * i <= n; i++) {
65 if (isPrime[i]) {
66 for (int j = i * i; j <= n; j += i) {
67 isPrime[j] = false;
68 }
69 }
70 }
71
72 return isPrime;
73}
74
75// μμΈμλΆν΄
76vector<pair<long long, int>> factorize(long long n) {
77 vector<pair<long long, int>> factors;
78
79 for (long long i = 2; i * i <= n; i++) {
80 if (n % i == 0) {
81 int cnt = 0;
82 while (n % i == 0) {
83 n /= i;
84 cnt++;
85 }
86 factors.push_back({i, cnt});
87 }
88 }
89
90 if (n > 1) {
91 factors.push_back({n, 1});
92 }
93
94 return factors;
95}
96
97// =============================================================================
98// 3. λͺ¨λλ¬ μ°μ°
99// =============================================================================
100
101// (a + b) % mod
102long long addMod(long long a, long long b, long long mod = MOD) {
103 return ((a % mod) + (b % mod)) % mod;
104}
105
106// (a * b) % mod
107long long mulMod(long long a, long long b, long long mod = MOD) {
108 return ((a % mod) * (b % mod)) % mod;
109}
110
111// (a ^ b) % mod (λΉ λ₯Έ κ±°λμ κ³±)
112long long powMod(long long a, long long b, long long mod = MOD) {
113 long long result = 1;
114 a %= mod;
115
116 while (b > 0) {
117 if (b & 1) {
118 result = mulMod(result, a, mod);
119 }
120 a = mulMod(a, a, mod);
121 b >>= 1;
122 }
123
124 return result;
125}
126
127// λͺ¨λλ¬ μμ (νλ₯΄λ§μ μμ 리, modκ° μμμΌ λ)
128long long modInverse(long long a, long long mod = MOD) {
129 return powMod(a, mod - 2, mod);
130}
131
132// λͺ¨λλ¬ μμ (νμ₯ μ ν΄λ¦¬λ)
133long long modInverseExtGcd(long long a, long long mod) {
134 auto [g, x, y] = extendedGcd(a, mod);
135 if (g != 1) return -1; // μμ μμ
136 return (x % mod + mod) % mod;
137}
138
139// =============================================================================
140// 4. μ‘°ν©λ‘
141// =============================================================================
142
143class Combination {
144private:
145 vector<long long> fact;
146 vector<long long> invFact;
147 long long mod;
148
149public:
150 Combination(int n, long long mod = MOD) : mod(mod) {
151 fact.resize(n + 1);
152 invFact.resize(n + 1);
153
154 fact[0] = 1;
155 for (int i = 1; i <= n; i++) {
156 fact[i] = mulMod(fact[i-1], i, mod);
157 }
158
159 invFact[n] = powMod(fact[n], mod - 2, mod);
160 for (int i = n - 1; i >= 0; i--) {
161 invFact[i] = mulMod(invFact[i+1], i + 1, mod);
162 }
163 }
164
165 // nCr
166 long long C(int n, int r) {
167 if (r < 0 || r > n) return 0;
168 return mulMod(fact[n], mulMod(invFact[r], invFact[n-r], mod), mod);
169 }
170
171 // nPr
172 long long P(int n, int r) {
173 if (r < 0 || r > n) return 0;
174 return mulMod(fact[n], invFact[n-r], mod);
175 }
176
177 // μΉ΄νλ μ
178 long long catalan(int n) {
179 return mulMod(C(2 * n, n), modInverse(n + 1, mod), mod);
180 }
181};
182
183// =============================================================================
184// 5. μ€μΌλ¬ νΌ ν¨μ
185// =============================================================================
186
187long long eulerPhi(long long n) {
188 long long result = n;
189
190 for (long long i = 2; i * i <= n; i++) {
191 if (n % i == 0) {
192 while (n % i == 0) {
193 n /= i;
194 }
195 result -= result / i;
196 }
197 }
198
199 if (n > 1) {
200 result -= result / n;
201 }
202
203 return result;
204}
205
206// 1~nκΉμ§ μ€μΌλ¬ νΌ ν¨μ
207vector<int> eulerPhiSieve(int n) {
208 vector<int> phi(n + 1);
209 iota(phi.begin(), phi.end(), 0);
210
211 for (int i = 2; i <= n; i++) {
212 if (phi[i] == i) { // iκ° μμ
213 for (int j = i; j <= n; j += i) {
214 phi[j] -= phi[j] / i;
215 }
216 }
217 }
218
219 return phi;
220}
221
222// =============================================================================
223// 6. μ€κ΅μΈμ λλ¨Έμ§ μ 리 (CRT)
224// =============================================================================
225
226// x β‘ a1 (mod m1), x β‘ a2 (mod m2)
227pair<long long, long long> crt(long long a1, long long m1,
228 long long a2, long long m2) {
229 auto [g, p, q] = extendedGcd(m1, m2);
230
231 if ((a2 - a1) % g != 0) {
232 return {-1, -1}; // ν΄ μμ
233 }
234
235 long long l = m1 / g * m2; // lcm
236 long long x = ((a1 + m1 * (((a2 - a1) / g * p) % (m2 / g))) % l + l) % l;
237
238 return {x, l};
239}
240
241// =============================================================================
242// 7. λ°λ¬-λΌλΉ μμ νμ (ν° μ)
243// =============================================================================
244
245long long mulModLarge(long long a, long long b, long long mod) {
246 return (__int128)a * b % mod;
247}
248
249long long powModLarge(long long a, long long b, long long mod) {
250 long long result = 1;
251 a %= mod;
252 while (b > 0) {
253 if (b & 1) result = mulModLarge(result, a, mod);
254 a = mulModLarge(a, a, mod);
255 b >>= 1;
256 }
257 return result;
258}
259
260bool millerRabin(long long n, long long a) {
261 if (n % a == 0) return n == a;
262
263 long long d = n - 1;
264 int r = 0;
265 while (d % 2 == 0) {
266 d /= 2;
267 r++;
268 }
269
270 long long x = powModLarge(a, d, n);
271 if (x == 1 || x == n - 1) return true;
272
273 for (int i = 0; i < r - 1; i++) {
274 x = mulModLarge(x, x, n);
275 if (x == n - 1) return true;
276 }
277
278 return false;
279}
280
281bool isPrimeLarge(long long n) {
282 if (n < 2) return false;
283 if (n == 2 || n == 3) return true;
284 if (n % 2 == 0) return false;
285
286 vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
287 for (long long a : witnesses) {
288 if (n == a) return true;
289 if (!millerRabin(n, a)) return false;
290 }
291 return true;
292}
293
294// =============================================================================
295// 8. μ½μ κ΄λ ¨
296// =============================================================================
297
298// μ½μ λͺ©λ‘
299vector<long long> getDivisors(long long n) {
300 vector<long long> divisors;
301
302 for (long long i = 1; i * i <= n; i++) {
303 if (n % i == 0) {
304 divisors.push_back(i);
305 if (i != n / i) {
306 divisors.push_back(n / i);
307 }
308 }
309 }
310
311 sort(divisors.begin(), divisors.end());
312 return divisors;
313}
314
315// μ½μ κ°μ
316int countDivisors(long long n) {
317 int count = 0;
318 for (long long i = 1; i * i <= n; i++) {
319 if (n % i == 0) {
320 count++;
321 if (i != n / i) count++;
322 }
323 }
324 return count;
325}
326
327// =============================================================================
328// ν
μ€νΈ
329// =============================================================================
330
331int main() {
332 cout << "============================================================" << endl;
333 cout << "μ μλ‘ μμ " << endl;
334 cout << "============================================================" << endl;
335
336 // 1. GCD / LCM
337 cout << "\n[1] GCD / LCM" << endl;
338 cout << " gcd(48, 18) = " << gcd(48, 18) << endl;
339 cout << " lcm(48, 18) = " << lcm(48, 18) << endl;
340 auto [g, x, y] = extendedGcd(48, 18);
341 cout << " 48*" << x << " + 18*" << y << " = " << g << endl;
342
343 // 2. μμ
344 cout << "\n[2] μμ νμ " << endl;
345 cout << " 17 is prime: " << (isPrime(17) ? "yes" : "no") << endl;
346 cout << " 100 is prime: " << (isPrime(100) ? "yes" : "no") << endl;
347
348 auto sieve = sieveOfEratosthenes(30);
349 cout << " 30 μ΄ν μμ: ";
350 for (int i = 2; i <= 30; i++) {
351 if (sieve[i]) cout << i << " ";
352 }
353 cout << endl;
354
355 // 3. μμΈμλΆν΄
356 cout << "\n[3] μμΈμλΆν΄" << endl;
357 cout << " 360 = ";
358 auto factors = factorize(360);
359 for (size_t i = 0; i < factors.size(); i++) {
360 cout << factors[i].first << "^" << factors[i].second;
361 if (i < factors.size() - 1) cout << " Γ ";
362 }
363 cout << endl;
364
365 // 4. λͺ¨λλ¬ μ°μ°
366 cout << "\n[4] λͺ¨λλ¬ μ°μ°" << endl;
367 cout << " 2^10 mod 1000 = " << powMod(2, 10, 1000) << endl;
368 cout << " 3μ μμ mod 7 = " << modInverse(3, 7) << endl;
369
370 // 5. μ‘°ν©λ‘
371 cout << "\n[5] μ‘°ν©λ‘ " << endl;
372 Combination comb(100);
373 cout << " C(10, 3) = " << comb.C(10, 3) << endl;
374 cout << " P(10, 3) = " << comb.P(10, 3) << endl;
375 cout << " Catalan(5) = " << comb.catalan(5) << endl;
376
377 // 6. μ€μΌλ¬ νΌ ν¨μ
378 cout << "\n[6] μ€μΌλ¬ νΌ ν¨μ" << endl;
379 cout << " Ο(12) = " << eulerPhi(12) << endl;
380 cout << " Ο(36) = " << eulerPhi(36) << endl;
381
382 // 7. CRT
383 cout << "\n[7] μ€κ΅μΈμ λλ¨Έμ§ μ 리" << endl;
384 auto [result, mod] = crt(2, 3, 3, 5);
385 cout << " x β‘ 2 (mod 3), x β‘ 3 (mod 5)" << endl;
386 cout << " x = " << result << " (mod " << mod << ")" << endl;
387
388 // 8. μ½μ
389 cout << "\n[8] μ½μ" << endl;
390 cout << " 36μ μ½μ: ";
391 for (auto d : getDivisors(36)) {
392 cout << d << " ";
393 }
394 cout << endl;
395 cout << " 36μ μ½μ κ°μ: " << countDivisors(36) << endl;
396
397 // 9. 볡μ‘λ μμ½
398 cout << "\n[9] 볡μ‘λ μμ½" << endl;
399 cout << " | μκ³ λ¦¬μ¦ | μκ°λ³΅μ‘λ |" << endl;
400 cout << " |-------------------|-------------------|" << endl;
401 cout << " | GCD (μ ν΄λ¦¬λ) | O(log min(a,b)) |" << endl;
402 cout << " | μμ νμ | O(βn) |" << endl;
403 cout << " | μλΌν μ€ν
λ€μ€ | O(n log log n) |" << endl;
404 cout << " | μμΈμλΆν΄ | O(βn) |" << endl;
405 cout << " | λΉ λ₯Έ κ±°λμ κ³± | O(log n) |" << endl;
406 cout << " | λ°λ¬-λΌλΉ | O(k logΒ² n) |" << endl;
407
408 cout << "\n============================================================" << endl;
409
410 return 0;
411}