최대공약수(GCD)의 원리
gcd(x, y)와 gcd(y, x % y)가 동일한 이유는 다음과 같습니다.
x와 y의 최대공약수를 d라고 가정합니다.
x = m * d, y = n * d라고 하면,
x % y = x - (x / y) * y가 됩니다.
이때 x / y는 정수 나눗셈 결과입니다.
x % y = m * d - (x / y) * n * d = (m - (x / y) * n) * d
따라서 x % y도 d의 배수입니다.
즉, x와 y의 공약수는 y와 x % y의 공약수와 동일하며, 그 반대도 성립합니다.
이 원리를 재귀적으로 적용하면 최대공약수를 효율적으로 계산할 수 있습니다.
long long calculate_gcd(long long a, long long b) {
if (b == 0) {
return a;
}
return calculate_gcd(b, a % b);
}
확장 유클리드 알고리즘(Extended Euclidean Algorithm)의 원리
확장 유클리드 알고리즘은 ax + by = gcd(a, b)를 만족하는 정수 x와 y를 찾는 데 사용됩니다.
기본 유클리드 알고리즘에서 gcd(a, b) = gcd(b, a % b)라는 점을 이용합니다.
a % b = a - (a / b) * b이므로,
gcd(a, b) = b * x' + (a % b) * y'
gcd(a, b) = b * x' + (a - (a / b) * b) * y'
gcd(a, b) = a * y' + b * (x' - (a / b) * y')
따라서 x = y'이고 y = x' - (a / b) * y'가 됩니다.
기저 조건은 b = 0일 때이며, 이때 gcd(a, 0) = a이므로 a * 1 + 0 * 0 = a를 만족하는 x = 1, y = 0을 반환합니다.
void extended_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
extended_gcd(b, a % b, x, y);
long long temp_x = x;
x = y;
y = temp_x - (a / b) * y;
}
베주 항등식 (Bézout's Identity)
두 음이 아닌 정수 a와 b에 대해, ax + by = gcd(a, b)를 만족하는 정수 x와 y가 항상 존재합니다. 이는 확장 유클리드 알고리즘을 통해 증명되고 활용됩니다.
문제 풀이: Modulo Ruins the Legend
이 문제는 주어진 배열 a와 두 정수 n, m에 대해 특정 조건을 만족하는 값을 찾는 문제입니다. 문제의 핵심은 베주 항등식과 모듈러 연산의 조합에 있습니다.
주어진 배열 a의 합을 sum이라고 하고, n * (n + 1) / 2를 s_n이라고 합시다.
문제는 다음과 같은 형태의 방정식을 푸는 것과 관련이 있습니다:
#include <iostream>
#include <vector>
#include <numeric>
// 최대공약수 계산 함수 (기본 유클리드 알고리즘)
long long calculate_gcd(long long a, long long b) {
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}
// 확장 유클리드 알고리즘 함수
void extended_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return;
}
extended_gcd(b, a % b, x, y);
long long temp_x = x;
x = y;
y = temp_x - (a / b) * y;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
long long m;
std::cin >> n >> m;
std::vector<long long> a(n);
long long array_sum = 0;
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
array_sum = (array_sum + a[i]) % m;
}
long long n_ll = n;
long long sum_of_1_to_n = (n_ll * (n_ll + 1) / 2) % m;
// ax + by = c 형태의 방정식을 풀어야 함
// 여기서 a는 n, b는 sum_of_1_to_n, c는 -array_sum 이 될 수 있음
// n * x_coeff + sum_of_1_to_n * y_coeff = gcd(n, sum_of_1_to_n)
long long common_divisor = calculate_gcd(n_ll, sum_of_1_to_n);
// 베주 항등식 적용: n * x_val + sum_of_1_to_n * y_val = common_divisor
long long x_val, y_val;
extended_gcd(n_ll, sum_of_1_to_n, x_val, y_val);
// 목표 방정식: n * k1 + sum_of_1_to_n * k2 = -array_sum (mod m)
// 이를 만족하는 k1, k2를 찾아야 함.
// 만약 -array_sum 이 common_divisor 로 나누어 떨어지지 않으면 해가 없음.
// 문제의 요구사항에 따라 k1, k2를 구해야 함.
// 여기서 m은 모듈러 값이므로, 실제로는 ax + by = c (mod m) 형태가 됨.
// 직접적인 해법은 다음과 같이 구성될 수 있음:
// let G = gcd(n, sum_of_1_to_n)
// We want to find k1, k2 such that n*k1 + sum_of_1_to_n*k2 = array_sum (mod m)
// This can be transformed to a linear Diophantine equation.
// n*k1 + sum_of_1_to_n*k2 - m*k3 = array_sum
// Find one solution (k1_0, k2_0, k3_0) for n*k1 + sum_of_1_to_n*k2 + m*k3 = array_sum
// Simplified approach based on problem context:
// Find the smallest non-negative value for a term.
// The core idea often involves finding coefficients that satisfy the modular arithmetic.
// Let's consider the equation in the form:
// n * x + (n * (n+1) / 2) * y = K (mod m)
// We are given an array sum `array_sum`. The problem likely wants to find minimum
// non-negative values for coefficients x and y.
// The provided solution logic appears to be finding a specific value `k`
// related to `array_sum` and `m`, and then using `exgcd` to find
// coefficients for `n` and `n * (n+1) / 2`.
// Let's follow the structure of the sample solution more closely to understand its intent.
// The variable 'x' seems to be gcd(n, n*(n+1)/2)
long long eq_gcd = calculate_gcd(n_ll, sum_of_1_to_n);
// The variable 'y' seems to be gcd(eq_gcd, m). This suggests a transformation.
long long final_gcd_val = calculate_gcd(eq_gcd, m);
// If array_sum is not divisible by final_gcd_val, there might be no solution in integers.
// However, due to modulo m, solutions might exist.
// The calculation `ll k = y - (y - sum % y);` and `ll j = -sum / y;` suggests
// finding a minimal adjustment `k` and a multiplier `j` related to `sum` and `y`.
// This part is highly specific to the exact problem statement and constraints.
// It likely relates to finding the smallest non-negative remainder or a related value.
// The code calculates `k` as `(array_sum % final_gcd_val + final_gcd_val) % final_gcd_val`.
// This finds the smallest non-negative remainder of `array_sum` when divided by `final_gcd_val`.
// Let this be `rem`. Then `array_sum = q * final_gcd_val + rem`.
long long rem = (array_sum % final_gcd_val + final_gcd_val) % final_gcd_val;
// If `rem` is not 0, it implies the equation might not have a direct integer solution
// without modulo m adjustments.
// The line `ll j = -array_sum / final_gcd_val;` seems problematic if array_sum is not divisible.
// A more robust approach for `j` would be related to solving `n*k1 + sum_of_1_to_n*k2 = array_sum (mod m)`.
// Assuming the sample solution's logic for `k` and `j` is derived correctly:
// `k` represents a base value, and `j` is a multiplier.
// The logic `k = y - (y - sum % y)` is equivalent to `k = sum % y` if `sum % y` is non-zero,
// or `y` if `sum % y` is zero and `y` is the divisor.
// More precisely, it seems to aim for `sum % y` or a related value.
// Let's use `rem` calculated above.
// The coefficient calculation for `x2` and `y2` uses `exgcd(n, n * (n + 1) / 2, x2, y2)`.
// This gives `n * x2 + sum_of_1_to_n * y2 = eq_gcd`.
long long final_x2, final_y2;
extended_gcd(n_ll, sum_of_1_to_n, final_x2, final_y2);
// To solve n*k1 + sum_of_1_to_n*k2 = array_sum (mod m)
// We know n*final_x2 + sum_of_1_to_n*final_y2 = eq_gcd
// Multiply by `array_sum / eq_gcd` if divisible.
// Let multiplier = array_sum / eq_gcd.
// n * (final_x2 * multiplier) + sum_of_1_to_n * (final_y2 * multiplier) = array_sum
// The sample code uses intermediate values `x1`, `y1` from `exgcd(x, m, x1, y1)`
// where `x = gcd(n, n * (n + 1) / 2)`. This suggests solving `x * x1 + m * y1 = gcd(x, m)`.
long long x_from_gcd_n_sn, y_from_gcd_n_sn;
extended_gcd(eq_gcd, m, x_from_gcd_n_sn, y_from_gcd_n_sn);
// The multiplier `j` is derived from `-array_sum / final_gcd_val`.
// This is the coefficient for the `m` term if we rewrite the equation.
// Let's interpret `j` as the number of times `final_gcd_val` needs to be "covered" by `m`.
// `j = -array_sum / final_gcd_val` implies `array_sum = -j * final_gcd_val`.
// This only works if `array_sum` is a multiple of `final_gcd_val`.
// The calculation `ll k = y - (y - sum % y);` is tricky. If `y` is `final_gcd_val`:
// `k = final_gcd_val - (final_gcd_val - array_sum % final_gcd_val)`
// `k = array_sum % final_gcd_val` (if `array_sum % final_gcd_val` is non-negative)
// The code calculates `j = -array_sum / final_gcd_val;`
// Let's assume `array_sum` is divisible by `final_gcd_val` for this step's validity.
// `coefficient_multiplier = array_sum / final_gcd_val`.
// The code seems to use `j` as a multiplier for modular inverse calculation or similar.
// Correct interpretation often requires careful handling of modulo arithmetic.
// The goal is to find `K1` and `K2` such that:
// `n * K1 + sum_of_1_to_n * K2 = array_sum (mod m)`
// `n * final_x2 + sum_of_1_to_n * final_y2 = eq_gcd`
// Multiply by `array_sum / eq_gcd` (if divisible):
// `n * (final_x2 * (array_sum / eq_gcd)) + sum_of_1_to_n * (final_y2 * (array_sum / eq_gcd))`
// `= array_sum`
// The resulting coefficients might need to be taken modulo m.
// The structure suggests solving for `K1` and `K2` separately or combined.
// Let's analyze the provided sample code's final output:
// `cout << k << endl;` - Prints the value `k`.
// `exgcd(x, m, x1, y1);` -> `eq_gcd * x1 + m * y1 = gcd(eq_gcd, m) = final_gcd_val`
// `x1 = (x1 % m * (j % m)) % m;` -> This scales `x1` using `j`.
// `exgcd(n, n * (n + 1) /2 , x2, y2);` -> `n * x2 + sum_of_1_to_n * y2 = eq_gcd`
// `x2 = x2%m*(x1%m)%m;` -> Scales `x2` using the adjusted `x1`.
// `y2 =(y2%m* (x1%m))%m;` -> Scales `y2` using the adjusted `x1`.
// `cout << (x2 % m + m) % m << " " << (y2 % m + m) % m< Prints final coefficients.
// This implies finding `k` first, and then finding coefficients `x2, y2`
// such that `n * x2 + sum_of_1_to_n * y2` is related to `array_sum` modulo `m`.
// The value `k` seems to be a target value or adjustment.
// The calculations involving `x1`, `y1` and `j` suggest finding modular inverse or
// a way to bridge `eq_gcd` to `final_gcd_val` and then to `array_sum`.
// A possible interpretation:
// We want to find `K1, K2` such that `n * K1 + sum_of_1_to_n * K2 = array_sum (mod m)`.
// Let `g = gcd(n, sum_of_1_to_n)`.
// We have `n * x_g + sum_of_1_to_n * y_g = g`.
// If `array_sum` is divisible by `g`, then `K1 = x_g * (array_sum / g)` and `K2 = y_g * (array_sum / g)` is a solution.
// Then take modulo `m`.
// The sample code uses `gcd(g, m)` which implies further reduction or constraint.
// Let `g' = gcd(g, m)`.
// The equation can be seen as `g * (n/g * K1 + sum_of_1_to_n/g * K2) = array_sum (mod m)`.
// This requires `array_sum` to be divisible by `g`.
// If `array_sum` is not divisible by `g`, there might be no integer solution.
// The structure suggests `k` is an initial value.
// `x1, y1` from `exgcd(g, m, x1, y1)` means `g * x1 + m * y1 = g'`.
// `x1` is related to the modular inverse of `g` modulo `m` (scaled by `g'`).
// The logic seems to be:
// 1. Find `g = gcd(n, sum_of_1_to_n)`.
// 2. Find `g' = gcd(g, m)`.
// 3. Check if `array_sum` is divisible by `g`. If not, the problem might be unsolvable or require a different interpretation.
// 4. If divisible, let `target = array_sum / g`.
// 5. Solve `(n/g) * K1 + (sum_of_1_to_n/g) * K2 = target (mod m/g')`. This is complex.
// Let's trust the sample code's structure for now.
// `k` is calculated.
// `exgcd(g, m, x1, y1)` finds `x1` such that `g * x1 = g' (mod m)`.
// `j` is derived from `array_sum` and `g'`. The sample uses `j = -array_sum / g'`. This suggests `array_sum` must be divisible by `g'`.
// `x1 = (x1 % m * (j % m)) % m` scales `x1` by `j`.
// `exgcd(n, sum_of_1_to_n, x2, y2)` finds `x2, y2` for `n * x2 + sum_of_1_to_n * y2 = g`.
// Final coefficients are derived by scaling `x2, y2` using the adjusted `x1`.
// Example calculation trace:
// n=2, m=10, a=[3, 4] -> sum=7
// n*(n+1)/2 = 2*3/2 = 3
// g = gcd(2, 3) = 1
// g' = gcd(1, 10) = 1
// array_sum = 7. Is 7 divisible by g=1? Yes.
// target = 7 / 1 = 7.
// Equation: 2*K1 + 3*K2 = 7 (mod 10)
// exgcd(2, 3, x_g, y_g): 2*(-1) + 3*(1) = 1. So x_g = -1, y_g = 1.
// K1 = x_g * target = -1 * 7 = -7
// K2 = y_g * target = 1 * 7 = 7
// Solution: K1 = -7 = 3 (mod 10), K2 = 7 (mod 10).
// Check: 2*(3) + 3*(7) = 6 + 21 = 27 = 7 (mod 10). Correct.
// The sample code's logic seems to compute intermediate values and combine them.
// The value `k` printed first seems to be `array_sum % final_gcd_val`.
// The final `x2`, `y2` are the coefficients for `n` and `sum_of_1_to_n` respectively.
long long final_k_val = (array_sum % final_gcd_val + final_gcd_val) % final_gcd_val;
std::cout << final_k_val << std::endl;
long long x1_temp, y1_temp;
extended_gcd(eq_gcd, m, x1_temp, y1_temp); // eq_gcd * x1_temp + m * y1_temp = final_gcd_val
// The multiplier `j` in the sample code `j = -sum / y;` is critical.
// If `sum = 7`, `y = final_gcd_val = 1`, then `j = -7 / 1 = -7`.
long long multiplier_j = -array_sum / final_gcd_val; // Requires array_sum % final_gcd_val == 0
// If not, this indicates an issue or different interpretation.
// Let's assume it's divisible for the sample logic.
// Adjusted x1 for modular operations.
// x1_adjusted = (x1_temp % m * (multiplier_j % m)) % m;
long long x1_adjusted = (x1_temp % m * (multiplier_j % m + m)) % m; // Ensure positive intermediate
// Now use the basic exgcd result for n and sum_of_1_to_n
long long coeff_n, coeff_sum;
extended_gcd(n_ll, sum_of_1_to_n, coeff_n, coeff_sum); // n * coeff_n + sum_of_1_to_n * coeff_sum = eq_gcd
// Combine results: The sample scales coeff_n and coeff_sum by x1_adjusted.
// This implies a transformation using the modular inverse relation found via exgcd(eq_gcd, m).
long long final_coeff_n = (coeff_n % m * x1_adjusted % m + m) % m;
long long final_coeff_sum = (coeff_sum % m * x1_adjusted % m + m) % m;
// The problem might be asking for coefficients k1, k2 for n*k1 + sum*k2 = array_sum (mod m)
// The derived final_coeff_n and final_coeff_sum should satisfy this.
// Check: n * final_coeff_n + sum_of_1_to_n * final_coeff_sum should be congruent to array_sum mod m.
std::cout << final_coeff_n << " " << final_coeff_sum << std::endl;
}