21_number_theory.c

Download
c 396 lines 11.4 KB 
  1/*
  2 * μ •μˆ˜λ‘  (Number Theory)
  3 * GCD/LCM, μ†Œμˆ˜, λͺ¨λ“ˆλŸ¬ μ—°μ‚°, μ‘°ν•©λ‘ 
  4 *
  5 * μˆ˜ν•™μ  μ•Œκ³ λ¦¬μ¦˜μ˜ κΈ°μ΄ˆμž…λ‹ˆλ‹€.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11#include <string.h>
 12#include <math.h>
 13
 14#define MOD 1000000007
 15#define MAX_N 100001
 16
 17/* =============================================================================
 18 * 1. GCD / LCM
 19 * ============================================================================= */
 20
 21long long gcd(long long a, long long b) {
 22    while (b) {
 23        long long temp = b;
 24        b = a % b;
 25        a = temp;
 26    }
 27    return a;
 28}
 29
 30long long gcd_recursive(long long a, long long b) {
 31    if (b == 0) return a;
 32    return gcd_recursive(b, a % b);
 33}
 34
 35long long lcm(long long a, long long b) {
 36    return a / gcd(a, b) * b;
 37}
 38
 39/* ν™•μž₯ μœ ν΄λ¦¬λ“œ μ•Œκ³ λ¦¬μ¦˜: ax + by = gcd(a, b) */
 40long long extended_gcd(long long a, long long b, long long* x, long long* y) {
 41    if (b == 0) {
 42        *x = 1;
 43        *y = 0;
 44        return a;
 45    }
 46    long long x1, y1;
 47    long long g = extended_gcd(b, a % b, &x1, &y1);
 48    *x = y1;
 49    *y = x1 - (a / b) * y1;
 50    return g;
 51}
 52
 53/* =============================================================================
 54 * 2. μ†Œμˆ˜ νŒλ³„ 및 체
 55 * ============================================================================= */
 56
 57bool is_prime(long long n) {
 58    if (n < 2) return false;
 59    if (n == 2) return true;
 60    if (n % 2 == 0) return false;
 61    for (long long i = 3; i * i <= n; i += 2) {
 62        if (n % i == 0) return false;
 63    }
 64    return true;
 65}
 66
 67/* μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체 */
 68bool* sieve_of_eratosthenes(int n) {
 69    bool* is_prime_arr = malloc((n + 1) * sizeof(bool));
 70    memset(is_prime_arr, true, n + 1);
 71    is_prime_arr[0] = is_prime_arr[1] = false;
 72
 73    for (int i = 2; i * i <= n; i++) {
 74        if (is_prime_arr[i]) {
 75            for (int j = i * i; j <= n; j += i) {
 76                is_prime_arr[j] = false;
 77            }
 78        }
 79    }
 80    return is_prime_arr;
 81}
 82
 83/* μ„ ν˜• 체 (μ†Œμˆ˜ λͺ©λ‘ 생성) */
 84int* linear_sieve(int n, int* prime_count) {
 85    int* spf = calloc(n + 1, sizeof(int));  /* smallest prime factor */
 86    int* primes = malloc((n + 1) * sizeof(int));
 87    *prime_count = 0;
 88
 89    for (int i = 2; i <= n; i++) {
 90        if (spf[i] == 0) {
 91            spf[i] = i;
 92            primes[(*prime_count)++] = i;
 93        }
 94        for (int j = 0; j < *prime_count && primes[j] <= spf[i] && i * primes[j] <= n; j++) {
 95            spf[i * primes[j]] = primes[j];
 96        }
 97    }
 98
 99    free(spf);
100    return primes;
101}
102
103/* μ†ŒμΈμˆ˜λΆ„ν•΄ */
104typedef struct {
105    int prime;
106    int count;
107} PrimeFactor;
108
109int factorize(long long n, PrimeFactor factors[]) {
110    int count = 0;
111    for (long long d = 2; d * d <= n; d++) {
112        if (n % d == 0) {
113            factors[count].prime = d;
114            factors[count].count = 0;
115            while (n % d == 0) {
116                factors[count].count++;
117                n /= d;
118            }
119            count++;
120        }
121    }
122    if (n > 1) {
123        factors[count].prime = n;
124        factors[count].count = 1;
125        count++;
126    }
127    return count;
128}
129
130/* =============================================================================
131 * 3. λͺ¨λ“ˆλŸ¬ μ—°μ‚°
132 * ============================================================================= */
133
134long long mod_add(long long a, long long b, long long mod) {
135    return ((a % mod) + (b % mod)) % mod;
136}
137
138long long mod_sub(long long a, long long b, long long mod) {
139    return ((a % mod) - (b % mod) + mod) % mod;
140}
141
142long long mod_mul(long long a, long long b, long long mod) {
143    return ((a % mod) * (b % mod)) % mod;
144}
145
146/* λΉ λ₯Έ κ±°λ“­μ œκ³± */
147long long mod_pow(long long base, long long exp, long long mod) {
148    long long result = 1;
149    base %= mod;
150    while (exp > 0) {
151        if (exp & 1) {
152            result = mod_mul(result, base, mod);
153        }
154        base = mod_mul(base, base, mod);
155        exp >>= 1;
156    }
157    return result;
158}
159
160/* λͺ¨λ“ˆλŸ¬ 역원 (페λ₯΄λ§ˆμ˜ μ†Œμ •λ¦¬, modκ°€ μ†Œμˆ˜μΌ λ•Œ) */
161long long mod_inverse(long long a, long long mod) {
162    return mod_pow(a, mod - 2, mod);
163}
164
165/* λͺ¨λ“ˆλŸ¬ 역원 (ν™•μž₯ μœ ν΄λ¦¬λ“œ) */
166long long mod_inverse_ext(long long a, long long mod) {
167    long long x, y;
168    long long g = extended_gcd(a, mod, &x, &y);
169    if (g != 1) return -1;  /* 역원 μ—†μŒ */
170    return (x % mod + mod) % mod;
171}
172
173/* λͺ¨λ“ˆλŸ¬ λ‚˜λˆ—μ…ˆ */
174long long mod_div(long long a, long long b, long long mod) {
175    return mod_mul(a, mod_inverse(b, mod), mod);
176}
177
178/* =============================================================================
179 * 4. μ‘°ν•©λ‘  (Combinatorics)
180 * ============================================================================= */
181
182long long factorial[MAX_N];
183long long inv_factorial[MAX_N];
184
185void precompute_factorials(int n, long long mod) {
186    factorial[0] = 1;
187    for (int i = 1; i <= n; i++) {
188        factorial[i] = mod_mul(factorial[i - 1], i, mod);
189    }
190    inv_factorial[n] = mod_inverse(factorial[n], mod);
191    for (int i = n - 1; i >= 0; i--) {
192        inv_factorial[i] = mod_mul(inv_factorial[i + 1], i + 1, mod);
193    }
194}
195
196/* nCr (mod p) */
197long long nCr(int n, int r, long long mod) {
198    if (r < 0 || r > n) return 0;
199    return mod_mul(factorial[n], mod_mul(inv_factorial[r], inv_factorial[n - r], mod), mod);
200}
201
202/* nPr (mod p) */
203long long nPr(int n, int r, long long mod) {
204    if (r < 0 || r > n) return 0;
205    return mod_mul(factorial[n], inv_factorial[n - r], mod);
206}
207
208/* 파슀칼의 μ‚Όκ°ν˜• (μž‘μ€ n용) */
209long long** pascal_triangle(int n) {
210    long long** C = malloc((n + 1) * sizeof(long long*));
211    for (int i = 0; i <= n; i++) {
212        C[i] = calloc(n + 1, sizeof(long long));
213        C[i][0] = 1;
214        for (int j = 1; j <= i; j++) {
215            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
216        }
217    }
218    return C;
219}
220
221/* =============================================================================
222 * 5. 였일러 ν”Ό ν•¨μˆ˜
223 * ============================================================================= */
224
225long long euler_phi(long long n) {
226    long long result = n;
227    for (long long p = 2; p * p <= n; p++) {
228        if (n % p == 0) {
229            while (n % p == 0) n /= p;
230            result -= result / p;
231        }
232    }
233    if (n > 1) result -= result / n;
234    return result;
235}
236
237/* 였일러 ν”Ό 체 */
238int* euler_phi_sieve(int n) {
239    int* phi = malloc((n + 1) * sizeof(int));
240    for (int i = 0; i <= n; i++) phi[i] = i;
241
242    for (int i = 2; i <= n; i++) {
243        if (phi[i] == i) {  /* i is prime */
244            for (int j = i; j <= n; j += i) {
245                phi[j] -= phi[j] / i;
246            }
247        }
248    }
249    return phi;
250}
251
252/* =============================================================================
253 * 6. μ€‘κ΅­μΈμ˜ λ‚˜λ¨Έμ§€ 정리 (CRT)
254 * ============================================================================= */
255
256/* x ≑ a1 (mod m1), x ≑ a2 (mod m2) */
257long long crt_two(long long a1, long long m1, long long a2, long long m2) {
258    long long x, y;
259    long long g = extended_gcd(m1, m2, &x, &y);
260
261    if ((a2 - a1) % g != 0) return -1;  /* ν•΄ μ—†μŒ */
262
263    long long lcm_val = m1 / g * m2;
264    long long result = a1 + m1 * ((a2 - a1) / g % (m2 / g) * x % (m2 / g));
265    return ((result % lcm_val) + lcm_val) % lcm_val;
266}
267
268/* =============================================================================
269 * 7. μ•½μˆ˜ κ΄€λ ¨
270 * ============================================================================= */
271
272int count_divisors(long long n) {
273    int count = 0;
274    for (long long i = 1; i * i <= n; i++) {
275        if (n % i == 0) {
276            count++;
277            if (i != n / i) count++;
278        }
279    }
280    return count;
281}
282
283long long sum_divisors(long long n) {
284    long long sum = 0;
285    for (long long i = 1; i * i <= n; i++) {
286        if (n % i == 0) {
287            sum += i;
288            if (i != n / i) sum += n / i;
289        }
290    }
291    return sum;
292}
293
294int* get_divisors(long long n, int* count) {
295    int* divisors = malloc(10000 * sizeof(int));
296    *count = 0;
297    for (long long i = 1; i * i <= n; i++) {
298        if (n % i == 0) {
299            divisors[(*count)++] = i;
300            if (i != n / i) divisors[(*count)++] = n / i;
301        }
302    }
303    return divisors;
304}
305
306/* =============================================================================
307 * ν…ŒμŠ€νŠΈ
308 * ============================================================================= */
309
310int compare_int(const void* a, const void* b) {
311    return *(int*)a - *(int*)b;
312}
313
314int main(void) {
315    printf("============================================================\n");
316    printf("μ •μˆ˜λ‘  (Number Theory) 예제\n");
317    printf("============================================================\n");
318
319    /* 1. GCD / LCM */
320    printf("\n[1] GCD / LCM\n");
321    printf("    gcd(48, 18) = %lld\n", gcd(48, 18));
322    printf("    lcm(12, 18) = %lld\n", lcm(12, 18));
323
324    long long x, y;
325    long long g = extended_gcd(35, 15, &x, &y);
326    printf("    35*%lld + 15*%lld = %lld (gcd)\n", x, y, g);
327
328    /* 2. μ†Œμˆ˜ */
329    printf("\n[2] μ†Œμˆ˜ νŒλ³„ 및 체\n");
330    printf("    is_prime(17) = %s\n", is_prime(17) ? "true" : "false");
331    printf("    is_prime(18) = %s\n", is_prime(18) ? "true" : "false");
332
333    int prime_count;
334    int* primes = linear_sieve(50, &prime_count);
335    printf("    50 μ΄ν•˜ μ†Œμˆ˜ (%d개): ", prime_count);
336    for (int i = 0; i < prime_count; i++) printf("%d ", primes[i]);
337    printf("\n");
338    free(primes);
339
340    /* 3. μ†ŒμΈμˆ˜λΆ„ν•΄ */
341    printf("\n[3] μ†ŒμΈμˆ˜λΆ„ν•΄\n");
342    PrimeFactor factors[20];
343    int factor_count = factorize(360, factors);
344    printf("    360 = ");
345    for (int i = 0; i < factor_count; i++) {
346        printf("%d^%d", factors[i].prime, factors[i].count);
347        if (i < factor_count - 1) printf(" Γ— ");
348    }
349    printf("\n");
350
351    /* 4. λͺ¨λ“ˆλŸ¬ μ—°μ‚° */
352    printf("\n[4] λͺ¨λ“ˆλŸ¬ μ—°μ‚°\n");
353    printf("    2^10 mod 1000 = %lld\n", mod_pow(2, 10, 1000));
354    printf("    3^(-1) mod 7 = %lld\n", mod_inverse(3, 7));
355    printf("    검증: 3 Γ— %lld mod 7 = %lld\n", mod_inverse(3, 7),
356           mod_mul(3, mod_inverse(3, 7), 7));
357
358    /* 5. μ‘°ν•©λ‘  */
359    printf("\n[5] μ‘°ν•©λ‘ \n");
360    precompute_factorials(1000, MOD);
361    printf("    10! = %lld\n", factorial[10]);
362    printf("    C(10, 3) = %lld\n", nCr(10, 3, MOD));
363    printf("    P(10, 3) = %lld\n", nPr(10, 3, MOD));
364
365    /* 6. 였일러 ν”Ό */
366    printf("\n[6] 였일러 ν”Ό ν•¨μˆ˜\n");
367    printf("    Ο†(12) = %lld\n", euler_phi(12));
368    printf("    Ο†(13) = %lld (μ†Œμˆ˜)\n", euler_phi(13));
369
370    /* 7. μ•½μˆ˜ */
371    printf("\n[7] μ•½μˆ˜\n");
372    printf("    28의 μ•½μˆ˜ 개수: %d\n", count_divisors(28));
373    printf("    28의 μ•½μˆ˜ ν•©: %lld\n", sum_divisors(28));
374    int div_count;
375    int* divisors = get_divisors(28, &div_count);
376    qsort(divisors, div_count, sizeof(int), compare_int);
377    printf("    28의 μ•½μˆ˜: ");
378    for (int i = 0; i < div_count; i++) printf("%d ", divisors[i]);
379    printf("\n");
380    free(divisors);
381
382    /* 8. λ³΅μž‘λ„ */
383    printf("\n[8] λ³΅μž‘λ„\n");
384    printf("    | μ•Œκ³ λ¦¬μ¦˜        | μ‹œκ°„λ³΅μž‘λ„    |\n");
385    printf("    |-----------------|---------------|\n");
386    printf("    | GCD (μœ ν΄λ¦¬λ“œ)  | O(log min)    |\n");
387    printf("    | μ†Œμˆ˜ νŒλ³„       | O(√n)         |\n");
388    printf("    | μ—λΌν† μŠ€ν…Œλ„€μŠ€  | O(n log log n)|\n");
389    printf("    | μ†ŒμΈμˆ˜λΆ„ν•΄      | O(√n)         |\n");
390    printf("    | κ±°λ“­μ œκ³±        | O(log exp)    |\n");
391
392    printf("\n============================================================\n");
393
394    return 0;
395}