結果
問題 |
No.1200 お菓子配り-3
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:10:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,169 ms / 4,000 ms |
コード長 | 7,299 bytes |
コンパイル時間 | 899 ms |
コンパイル使用メモリ | 93,784 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-05-14 13:12:04 |
合計ジャッジ時間 | 15,929 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <numeric> #include <algorithm> #include <vector> // Ensure vector header is included // Function to find all positive divisors of n // Input n can be negative, zero, or positive. Finds divisors of |n|. // If n=0, returns an empty vector as there are no positive divisors. // Technically 0 is divisible by any non-zero integer, but the problem context implies positive divisors. std::vector<long long> get_divisors(long long n) { // Take the absolute value since we are interested in positive divisors. n = std::abs(n); std::vector<long long> divisors; // If n is 0, it has no positive divisors according to standard definitions. // The case X-Y=0 (meaning X=Y) is handled separately where this function isn't called on 0. if (n == 0) return divisors; // Iterate from 1 up to sqrt(n). // Using i * i <= n avoids potential floating point issues with sqrt() and is generally safer. for (long long i = 1; i * i <= n; ++i) { // If i divides n if (n % i == 0) { // Add divisor i divisors.push_back(i); // If i*i != n, then n/i is a distinct divisor. Add it too. // This avoids adding the square root twice if n is a perfect square. if (i * i != n) { divisors.push_back(n / i); } } } // The divisors are not necessarily sorted, but sorting is not required for the logic. return divisors; } int main() { // Use fast I/O operations std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int S; // Number of test cases std::cin >> S; while (S--) { long long X, Y; // Input chocolates and cookies counts std::cin >> X >> Y; long long count = 0; // Initialize count of valid (A, B, C) triplets // Case 1: X equals Y if (X == Y) { // Subcase A = 1: // The equations become X = B + C and Y = C + B, which are identical: X = B + C. // We need positive integers B, C such that B + C = X. // This is possible if X >= 2. B can range from 1 to X-1. C = X-B is then fixed and >= 1. // So there are X-1 solutions for A=1 if X >= 2. if (X >= 2) { count = X - 1; } else { // If X=1, Y=1, then B+C=1 has no solutions with B>=1, C>=1. count = 0; } // Subcase A > 1: // Necessary and sufficient conditions are: // 1. A > 1 // 2. A+1 divides X+Y = 2X // 3. A-1 divides X-Y = 0 (always true for A>1) // 4. If A is odd, an additional condition applies: (X+Y)/(A+1) + (X-Y)/(A-1) must be even. // Since X-Y=0, this simplifies to (2X)/(A+1) + 0 must be even. // This means (2X)/(A+1) = 2k for some integer k, which simplifies to X/(A+1) = k, i.e., A+1 must divide X. long long twoX = 2 * X; // Find all positive divisors k1 of 2X. k1 represents A+1. std::vector<long long> k1_divisors = get_divisors(twoX); for (long long k1 : k1_divisors) { // k1 is a positive divisor of 2X. // We require A > 1, which means k1 = A+1 must be greater than 2. if (k1 <= 2) continue; long long A = k1 - 1; // A >= 2 holds because k1 > 2. // Positivity checks AX > Y and AY > X become AX > X because Y=X. // Since X >= 1 and A >= 2, AX >= 2*X. // If X >= 1, 2X >= X + X >= X + 1 > X. So AX > X always holds. No explicit check needed. if (A % 2 != 0) { // If A is odd // Additional check for odd A: k1 = A+1 must divide X if (X % k1 == 0) { count++; // Increment count if condition met } } else { // If A is even // No additional check needed for even A count++; // Increment count } } } else { // Case 2: X is not equal to Y // A=1 is impossible if X != Y because X = B+C and Y = C+B would imply X=Y. // Start count from 0. Only consider A > 1. count = 0; long long diff = X - Y; // Difference X-Y, can be negative long long sum = X + Y; // Sum X+Y, always positive since X, Y >= 1 // Necessary and sufficient conditions for A > 1: // 1. A+1 divides X+Y // 2. A-1 divides X-Y // 3. Positivity: AX > Y and AY > X // 4. If A is odd, ( (X+Y)/(A+1) + (X-Y)/(A-1) ) must be even. // We iterate through positive divisors k2 of |X-Y|. k2 represents A-1. std::vector<long long> k2_divisors = get_divisors(diff); for (long long k2 : k2_divisors) { // k2 is a positive divisor of |X-Y|. Since X != Y, |X-Y| >= 1, so k2 >= 1. long long A = k2 + 1; // A = k2+1 >= 2, so A > 1 is guaranteed. long long k1 = A + 1; // k1 = k2 + 2 >= 3 holds. // Check primary divisibility condition: k1 divides X+Y // Check k1 != 0 implicitly: k1 >= 3 always. Division by zero is not a risk. if (sum % k1 == 0) { // `sum` could be large, but fits in long long. `k1` fits in long long. Modulo is safe. // Check positivity conditions: AX > Y and AY > X // Use 1LL to force 64-bit multiplication to avoid overflow with large A, X, Y. // The maximum product 1LL * A * X can be around (5e8+1)*5e8 ~ 2.5e17, which fits within signed 64-bit range (~9e18). bool pos_check = (1LL * A * X > Y && 1LL * A * Y > X); if (pos_check) { // If both positivity conditions are met if (A % 2 != 0) { // If A is odd // Additional check for odd A: (n+m) must be even long long n = sum / k1; // Integer division is exact since sum % k1 == 0 long long m = diff / k2; // Integer division is exact since k2 divides |diff| // The sign of m matches the sign of diff = X-Y. // Check if (n+m) is even. The modulo operator % handles negative numbers correctly in C++ for this check. if ((n + m) % 2 == 0) { count++; // Increment count if condition met } } else { // If A is even // No additional check needed for even A count++; // Increment count } } } } } // Output the total count for the current test case std::cout << count << "\n"; } return 0; }