#1084044 (C++17) No.849 yuki国の分割統治

• 問題: No.849 yuki国の分割統治
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:15:40
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 54 ms / 2,000 ms
• コード長: 7,081 bytes
• コンパイル時間: 1,260 ms
• コンパイル使用メモリ: 107,980 KB
• 実行使用メモリ: 9,984 KB
• 最終ジャッジ日時: 2025-05-14 13:17:00
• 合計ジャッジ時間: 3,742 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 26

ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <utility> // std::pair
#include <numeric> // std::gcd
#include <cmath>   // std::abs
#include <string>  // For printing __int128_t (optional, mainly for debugging)
#include <algorithm> // For std::reverse in __int128_t printing helper

// Use __int128_t type for calculations that might exceed 64 bits
using int128 = __int128_t;

// Function to compute GCD for long long integers.
// std::gcd requires non-negative arguments in some older standards/versions.
// C++17 std::gcd handles signed integers correctly, returning non-negative result.
// Using std::abs for safety and clarity.
long long compute_gcd(long long x, long long y) {
    return std::gcd(std::abs(x), std::abs(y));
}

// Function for modular arithmetic that correctly handles negative results of % operator.
// Assumes mod > 0.
long long safe_modulo(long long val, long long mod) {
    // Check for modulo by zero, although logic should prevent this.
    if (mod == 0) {
         // Based on problem logic D_abs > 0 for D!=0 case.
         // This path indicates an issue. Return 0 or handle error.
         return 0; 
    }
    // The C++ % operator can return negative results for negative input 'val'.
    long long res = val % mod;
    // Adjust negative result to be in [0, mod-1]
    if (res < 0) {
        res += mod;
    }
    return res;
}

// Similar function for __int128_t type. Assumes mod > 0.
int128 safe_modulo128(int128 val, int128 mod) {
     // Check for modulo by zero, although logic should prevent this.
     if (mod == 0) {
         // Based on problem logic M > 0 for D=0 case.
         // This path indicates an issue. Return 0 or handle error.
         return 0;
     }
    // The C++ % operator can return negative results for negative input 'val'.
    int128 res = val % mod;
    // Adjust negative result to be in [0, mod-1]
    if (res < 0) {
        res += mod;
    }
    return res;
}

// Helper function to print __int128_t. This is useful for debugging purposes.
// Standard iostream doesn't support __int128_t directly.
std::ostream& operator<<(std::ostream& os, int128 val) {
    if (val == 0) return os << "0";
    std::string s = "";
    bool neg = false;
    if (val < 0) {
        neg = true;
        val = -val; // Make positive for digit extraction
    }
    while (val > 0) {
        s += (char)('0' + (val % 10));
        val /= 10;
    }
    if (neg) os << "-"; // Print sign if negative
    std::reverse(s.begin(), s.end()); // Digits are extracted in reverse order
    return os << s;
}


int main() {
    // Faster I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long a, b, c, d;
    std::cin >> a >> b >> c >> d;

    int N;
    std::cin >> N;

    std::vector<std::pair<long long, long long>> P(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i].first >> P[i].second;
    }

    // Compute determinant D = ad - bc. Use __int128_t to avoid overflow during multiplication.
    int128 D_128 = (int128)a * d - (int128)b * c;
    
    // The final value of D fits within long long based on analysis.
    long long D = (long long)D_128; 

    if (D != 0) {
        // Case 1: Vectors v1=(a,b) and v2=(c,d) are linearly independent.
        // The equivalence classes are determined by coordinates modulo D.
        long long D_abs = std::abs(D);
        // Since D != 0, D_abs must be > 0. No need to check for D_abs == 0.

        // Use a set to store unique pairs representing groups.
        std::set<std::pair<long long, long long>> distinct_groups;

        for (int i = 0; i < N; ++i) {
            long long x_i = P[i].first;
            long long y_i = P[i].second;

            // Calculate the transformed coordinates (X_i, Y_i). Need long long for intermediate products.
            long long X_i = (long long)d * x_i - (long long)c * y_i;
            long long Y_i = (long long)a * y_i - (long long)b * x_i;

            // Compute the canonical representative pair modulo D_abs.
            long long R1 = safe_modulo(X_i, D_abs);
            long long R2 = safe_modulo(Y_i, D_abs);

            // Insert the pair into the set. The set automatically handles uniqueness.
            distinct_groups.insert({R1, R2});
        }
        // The size of the set is the number of distinct groups.
        std::cout << distinct_groups.size() << std::endl;

    } else { // D == 0
        // Case 2: Vectors v1=(a,b) and v2=(c,d) are linearly dependent (parallel).
        // The lattice L is 1-dimensional, generated by a vector v = G*u.
        
        // Calculate gcd for v1=(a,b). It's guaranteed > 0 because (a,b)!=(0,0).
        long long g = compute_gcd(a, b); 
        
        // Calculate the primitive vector u parallel to v1.
        long long u_x = 0, u_y = 0;
        if (g != 0) { // This check is technically redundant due to constraints.
             u_x = a / g;
             u_y = b / g;
        } 

        // Calculate gcd for v2=(c,d). Guaranteed > 0 because (c,d)!=(0,0).
        long long h = compute_gcd(c, d); 

        // Canonicalize the primitive vector u.
        // Ensure uniqueness: first non-zero component positive, or if first is zero, second positive.
        if (u_x < 0 || (u_x == 0 && u_y < 0)) {
            u_x = -u_x;
            u_y = -u_y;
        }
        
        // Calculate G = gcd(g, h). Guaranteed > 0 since g, h > 0.
        long long G = compute_gcd(g, h); 

        // Calculate the modulus M = G * ||u||^2 using __int128_t to avoid overflow.
        int128 G_128 = G;
        int128 u_x_128 = u_x;
        int128 u_y_128 = u_y;
        // Norm squared ||u||^2 = u_x^2 + u_y^2. It must be > 0 since u is primitive for a non-zero vector.
        int128 u_norm_sq = u_x_128 * u_x_128 + u_y_128 * u_y_128;
        int128 M = G_128 * u_norm_sq; // M > 0 based on logic.

        // Use a set to store unique pairs representing groups. Pair uses long long and __int128_t.
        std::set<std::pair<long long, int128>> distinct_groups;
        
        for (int i = 0; i < N; ++i) {
            long long x_i = P[i].first;
            long long y_i = P[i].second;

            // Calculate invariant K'_i (related to projection onto line perpendicular to u).
            // Fits within long long.
            long long K_prime_i = (long long)x_i * u_y - (long long)y_i * u_x;
            
            // Calculate invariant S_i (related to projection onto line parallel to u).
            // Fits within long long.
            long long S_i = (long long)x_i * u_x + (long long)y_i * u_y;
             
            // Compute the canonical representative S_i mod M using __int128_t.
            int128 S_i_128 = S_i;
            int128 R_S = safe_modulo128(S_i_128, M); 
            // Note: If M=1, R_S will correctly be 0.
            
            // Insert the pair (K'_i, R_S) into the set.
            distinct_groups.insert({K_prime_i, R_S});
        }
        // The size of the set is the number of distinct groups.
        std::cout << distinct_groups.size() << std::endl;
    }

    return 0;
}