結果
| 問題 |
No.1200 お菓子配り-3
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 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;
}