結果
| 問題 |
No.2119 一般化百五減算
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:12:00 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 22 ms / 2,000 ms |
| コード長 | 11,256 bytes |
| コンパイル時間 | 652 ms |
| コンパイル使用メモリ | 93,332 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:31 |
| 合計ジャッジ時間 | 1,671 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric> // Provides std::gcd in C++17, but we implement our own for clarity/compatibility
#include <limits> // For std::numeric_limits
#include <cmath> // For std::abs
// Use long long for potentially large numbers involved in CRT calculations
typedef long long ll;
// Function to compute the greatest common divisor (GCD) using the Euclidean algorithm
// Ensures non-negative inputs are used.
ll custom_gcd(ll a, ll b) {
a = std::abs(a);
b = std::abs(b);
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}
// Structure to hold the result of the Extended Euclidean Algorithm
struct ExtGCDResult {
ll g; // gcd(a, b)
ll x; // coefficient of a
ll y; // coefficient of b
// Satisfies ax + by = g
};
// Extended Euclidean Algorithm implementation
// Returns {g, x, y} such that ax + by = g = gcd(a, b)
// Assumes a, b are non-negative, which is true for the context it's used in this problem.
ExtGCDResult extgcd(ll a, ll b) {
if (b == 0) {
// Base case: gcd(a, 0) = a. Then ax + 0y = a. Choose x=1, y=0.
return {a, 1, 0};
}
// Recursive step: Compute extgcd for (b, a % b)
ExtGCDResult res = extgcd(b, a % b);
// From result {g, x', y'} for bx' + (a % b)y' = g
// We derive x, y for ax + by = g
// Substitute a % b = a - floor(a/b) * b
// g = bx' + (a - (a / b) * b)y'
// g = bx' + ay' - (a / b) * b * y'
// g = ay' + b(x' - (a / b) * y')
// So x = y' and y = x' - (a / b) * y'
ll x = res.y;
ll y = res.x - (a / b) * res.y;
return {res.g, x, y};
}
// Function to merge two congruences:
// n = R (mod L)
// n = C (mod B)
// Finds the smallest non-negative solution n satisfying both, subject to n <= N.
// Returns a pair {new_R, new_L}.
// new_L = -1 indicates no solution exists.
// new_L = -2 indicates a candidate solution was found because the LCM exceeds N,
// and this candidate must be verified against remaining congruences.
// Otherwise, {new_R, new_L} represents the combined congruence n = new_R (mod new_L).
std::pair<ll, ll> merge_congruences(ll R, ll L, ll C, ll B, ll N) {
// Normalize C to be non-negative: C becomes C mod B in range [0, B-1]
C = (C % B + B) % B;
// Calculate g = gcd(L, B)
ll g = custom_gcd(L, B);
// Check compatibility condition: R must be congruent to C modulo g
// Need to ensure R % g and C % g results are handled correctly if negative, using (val % g + g) % g
if ((R % g + g) % g != (C % g + g) % g) {
// Congruences are contradictory
return {-1, -1}; // No solution
}
// From the first congruence, n = R + k*L for some integer k.
// Substitute into the second congruence: R + k*L = C (mod B)
// k*L = C - R (mod B)
// This linear congruence has solutions for k because C - R is divisible by g = gcd(L, B).
// Divide by g: k * (L/g) = (C - R)/g (mod B/g)
ll L_div_g = L / g;
ll B_div_g = B / g;
ll C_minus_R = C - R;
// C-R is guaranteed to be divisible by g from the compatibility check
ll C_minus_R_div_g = C_minus_R / g;
// Find modular inverse of (L/g) modulo (B/g) using Extended Euclidean Algorithm
// Since gcd(L/g, B/g) = gcd(L, B)/g = g/g = 1, the inverse exists.
ExtGCDResult res_inv = extgcd(L_div_g, B_div_g);
// res_inv.g should be 1. If not, something is wrong.
if (res_inv.g != 1) {
// This indicates an issue, potentially large number related or logic error
return {-1, -1};
}
// The inverse is res_inv.x. Normalize it to be in [0, B/g - 1]
ll inv = (res_inv.x % B_div_g + B_div_g) % B_div_g;
// Solve for k: k = (C - R)/g * inv (mod B/g)
// Calculate k0, the smallest non-negative solution for k.
// Need careful modular multiplication, especially if C_minus_R_div_g is negative.
ll k0_term1 = C_minus_R_div_g;
ll k0_term2 = inv;
// Compute (k0_term1 * k0_term2) % B_div_g ensuring non-negative result.
ll k0_term1_mod = (k0_term1 % B_div_g + B_div_g) % B_div_g;
ll k0_term2_mod = k0_term2; // inv is already non-negative and < B_div_g
// Check for potential overflow before multiplication
ll k0_prod;
bool k0_prod_overflow = false;
const ll LLONG_MAX_VAL = std::numeric_limits<long long>::max();
if (k0_term1_mod > 0 && k0_term2_mod > 0 && k0_term1_mod > LLONG_MAX_VAL / k0_term2_mod) {
k0_prod_overflow = true;
} else {
k0_prod = k0_term1_mod * k0_term2_mod;
}
if (k0_prod_overflow) {
// Should not happen with given constraints. If it does, implies intermediate values are too large.
return {-1, -1};
}
ll k0 = k0_prod % B_div_g; // Smallest non-negative k solution modulo B/g
// The combined congruence is n = R' (mod L'), where L' = lcm(L, B)
// Calculate the new modulus L' = lcm(L, B) = (L / g) * B
ll new_L;
bool L_overflow = false;
// Check for overflow before calculating L' = (L/g) * B
if (B == 0) L_overflow = true; // B must be positive based on constraints
// Check if L/g > LLONG_MAX / B
else if (L_div_g > 0 && B > 0 && L_div_g > LLONG_MAX_VAL / B) {
L_overflow = true;
} else {
new_L = L_div_g * B;
}
// Calculate the smallest non-negative solution R' for the combined system.
// R' = R + k0 * L
ll k0L_prod;
bool k0L_overflow = false;
// Check for overflow before calculating k0 * L
if (L == 0) k0L_prod = 0; // L cannot be 0 after first step
else if (k0 > 0 && L > 0 && k0 > LLONG_MAX_VAL / L) {
k0L_overflow = true;
} else {
k0L_prod = k0 * L;
}
if (k0L_overflow) {
// Product k0*L overflows long long, meaning the result R' is huge.
// Since N is relatively small (<= 10^5), R' > N.
return {-1, -1}; // No solution <= N
}
// Calculate R' = R + k0*L checking for overflow during addition
ll new_R;
bool R_add_overflow = false;
if (k0L_prod > LLONG_MAX_VAL - R) { // Check R + k0L_prod > LLONG_MAX
R_add_overflow = true;
} else {
new_R = R + k0L_prod;
}
if (R_add_overflow) {
// Final R' overflows long long. Result must be > N.
return {-1, -1}; // No solution <= N
}
// Now we have the smallest non-negative solution `new_R` and the new modulus `new_L`.
// Check if the new modulus `new_L` exceeds N or overflowed.
if (L_overflow || new_L > N) {
// If L' > N, then `new_R` is the only possible solution candidate <= N.
// We must check if `new_R` itself is <= N.
if (new_R > N) {
// The smallest non-negative solution is already > N.
return {-1, -1}; // No solution <= N
} else {
// `new_R` is a valid candidate <= N. Return it with flag -2 to enter candidate mode.
return {new_R, -2};
}
} else {
// new_L is within limits and <= N. The combined congruence is n = new_R (mod new_L).
// The smallest non-negative solution is new_R. It should satisfy new_R < new_L.
// Since new_L <= N, it follows that new_R <= N.
// However, let's double-check if new_R could exceed N. Example: N=100, L=60, B=70. lcm(60, 70)=420. If new_R is computed and L'=420, the check L' > N triggers.
// If L=30, B=20. lcm(30, 20)=60. If N=50. L'=60 > N. Check triggers.
// What if L=10, B=12. lcm(10, 12)=60. N=100. L'=60 <= N. Suppose R=1, C=5. g=2. R=1, C=5. 1%2=1, 5%2=1. Compatible. L/g=5, B/g=6. C-R/g = (5-1)/2=2. extgcd(5, 6) -> 5x+6y=1. x=-1, y=1. inv = -1 mod 6 = 5. k0 = (2 * 5) % 6 = 10 % 6 = 4. R'=R+k0*L = 1 + 4*10 = 41. new_L=60. N=100. new_L<=N. return {41, 60}. Okay.
// Final check: if minimal solution new_R > N. This might happen if intermediate N wasn't considered properly.
if (new_R > N) {
return {-1, -1};
}
// Return the updated state {R, L}
return {new_R, new_L};
}
}
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
ll N; // Upper bound for the solution (non-negative integer)
int M; // Number of congruences (positive integer)
std::cin >> N >> M;
// M is guaranteed to be at least 1.
ll R; // Current remainder for the combined congruence
ll L; // Current modulus for the combined congruence
ll B, C; // Modulus and remainder for the next congruence to merge
// Read the first congruence to initialize R and L
std::cin >> B >> C;
if (B <= 0) { // Modulus must be positive
std::cout << "NaN" << std::endl;
return 0;
}
// Initialize R = C mod B, ensuring R is non-negative [0, B-1]
R = (C % B + B) % B;
L = B; // Initial modulus is B0
// Check if the smallest non-negative solution from the first congruence already exceeds N
if (R > N) {
std::cout << "NaN" << std::endl;
return 0;
}
// Flag and value for candidate mode (when LCM exceeds N)
bool candidate_mode = false;
ll candidate_val = -1;
// Process remaining M-1 congruences
for (int m = 1; m < M; ++m) {
std::cin >> B >> C;
if (B <= 0) { // Modulus must be positive
std::cout << "NaN" << std::endl;
return 0;
}
if (candidate_mode) {
// If already in candidate mode, just verify the candidate against the current congruence.
ll C_norm = (C % B + B) % B; // Normalize C
// Check if candidate_val satisfies n = C (mod B)
// Check (candidate_val % B + B) % B == C_norm carefully
if ((candidate_val % B + B) % B != C_norm) {
// Candidate failed verification
std::cout << "NaN" << std::endl;
return 0;
}
// If verification passes, continue to the next congruence. Candidate remains the same.
} else {
// Not in candidate mode. Try to merge the current congruence (R, L) with (C, B).
std::pair<ll, ll> result = merge_congruences(R, L, C, B, N);
if (result.second == -1) { // merge_congruences reported no solution
std::cout << "NaN" << std::endl;
return 0;
} else if (result.second == -2) { // merge_congruences found a candidate and activated candidate mode
candidate_mode = true;
candidate_val = result.first;
} else { // Normal update: merge successful, L remains <= N. Update R and L.
R = result.first;
L = result.second;
// R = result.first should already be <= N based on checks in merge_congruences
}
}
}
// After processing all congruences:
if (candidate_mode) {
// If we ended in candidate mode, the verified candidate is the answer.
std::cout << candidate_val << std::endl;
} else {
// If we never entered candidate mode, the final R is the answer.
// R is guaranteed to be the smallest non-negative solution and <= N.
std::cout << R << std::endl;
}
return 0;
}