結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0