3-1 CRT

A를 만족하는 가장 작은 음이 아닌 정수 값을 구하시오. 에이에서 에이는 모든 값이다.

#include<stdio.h> typedef long long int int64; int64 Ni[10], Bi[10]; int64 inv(int64 a, int64 m) { int64 m0 = m, t, q, x0 = 0, x1 = 1; if (m == 1) return 0; while (a > 1) { q = a / m; t = m, m = a % m, a = t; t = x0, x0 = x1 - q * x0, x1 = t; } if (x1 < 0) x1 += m0; return x1; } int64 findMinX(int64 *a, int64 *m, int k) { int i; int64 prod = 1, result = 0, pp; for (i = 0; i < k; i++) prod *= a[i]; for (i = 0; i < k; i++) { pp = prod / a[i]; result += m[i] * inv(pp, a[i]) * pp; } return result % prod; } int main() { freopen("text.txt", "r", stdin); int T, t, n, i; scanf("%d", &T); for (t = 1; t <= T; ++t) { scanf("%d", &n); for (i = 0; i < n; ++i) scanf("%lld %lld", &Bi[i], &Ni[i]); printf("#%d %lld\n", t, findMinX(Ni, Bi, n)); } return 0; }

- 코드 이해가 - 함수 2개 일 뿐인데 - 변수가 많음 - 그래도 가장 풀어쓴 코드를 먼저 찾아서 보는게 좋을까