結果

問題 No.1627 三角形の成立
ユーザー 👑 null
提出日時 2025-02-02 16:49:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 97 ms / 1,000 ms
コード長 4,180 bytes
コンパイル時間 4,426 ms
コンパイル使用メモリ 277,560 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-02-02 16:49:22
合計ジャッジ時間 6,468 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const ll MOD = 1000000007;
 
// Modular exponentiation.
ll modExp(ll a, ll b, ll mod=MOD) {
    ll res = 1 % mod;
    a %= mod;
    while(b) {
        if(b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
// Modular inverse (mod is prime).
ll modInv(ll a, ll mod=MOD){
    return modExp(a, mod-2, mod);
}
 
// Compute binomial coefficient C(x,3) modulo MOD.
ll comb3(ll x) {
    if(x < 3) return 0;
    ll inv6 = modInv(6);
    return (((x % MOD) * ((x-1) % MOD)) % MOD * ((x-2) % MOD) % MOD * inv6) % MOD;
}
 
// Compute the Möbius function for all numbers up to N.
vector<int> mobiusSieve(int N) {
    vector<int> mu(N+1, 1);
    vector<int> prime;
    vector<int> mark(N+1, 0);
    for (int i = 2; i <= N; i++){
        if (!mark[i]){
            prime.push_back(i);
            mu[i] = -1;
        }
        for (int p: prime){
            if(i*p > N) break;
            mark[i*p] = 1;
            if(i % p == 0){
                mu[i*p] = 0;
                break;
            } else {
                mu[i*p] = -mu[i];
            }
        }
    }
    return mu;
}
 
// Main: count triangles in an n x m grid.
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll n, m;
    cin >> n >> m;
    // Total number of lattice points.
    ll totalPoints = n * m;
    // Total ways to choose 3 points.
    ll totalTrip = comb3(totalPoints);
 
    // Count collinear triples on horizontal lines.
    ll horiz = (n % MOD) * comb3(m) % MOD;
    // Count collinear triples on vertical lines.
    ll vert = (m % MOD) * comb3(n) % MOD;
 
    // Now count collinear triples on lines with nonzero, non‐infinite slope.
    // We wish to compute
    //    nonAxis = 2 * sum_{dx=1}^{n-1} sum_{dy=1}^{m-1} (gcd(dx,dy)-1)*(n-dx)*(m-dy).
    // Change variable: let dx = d*i, dy = d*j with gcd(i,j)=1.
    // Then set D = min(n-1, m-1) so that d runs 1...D.
    ll D = min(n - 1, m - 1);
    ll S_nonAxis = 0;
 
    // We need the Möbius function up to D.
    vector<int> mu = mobiusSieve((int)D);
 
    // For each d from 1 to D, let A = floor((n-1)/d) and B = floor((m-1)/d).
    // Then define:
    //   F(d) = sum_{1<=i<=A, 1<=j<=B, gcd(i,j)=1} (n - d*i)*(m - d*j)
    // and add (d-1)*F(d) to our total.
    for (ll d = 1; d <= D; d++){
        ll A = (n - 1) / d;
        ll B = (m - 1) / d;
        if(A == 0 || B == 0) continue;
 
        ll F_val = 0;
        ll lim = min(A, B);
        // Möbius inversion: sum over k from 1 to lim.
        for (ll k = 1; k <= lim; k++){
            if(mu[k] == 0) continue;
            ll A2 = A / k;
            ll B2 = B / k;
            // We need:
            //   G = sum_{i=1}^{A2} sum_{j=1}^{B2} (n - d*k*i)*(m - d*k*j)
            // Because the summand is separable we write:
            //   G = ( n*A2 - d*k * (1+2+...+A2) )
            //       * ( m*B2 - d*k * (1+2+...+B2) )
            ll sum_i = (A2 * (A2 + 1) / 2) % MOD;
            ll sum_j = (B2 * (B2 + 1) / 2) % MOD;
 
            ll part1 = ((n % MOD) * (A2 % MOD)) % MOD;
            ll t2 = ((d % MOD) * (k % MOD)) % MOD;
            t2 = (t2 * sum_i) % MOD;
            part1 = (part1 - t2) % MOD;
            if(part1 < 0) part1 += MOD;
 
            ll part2 = ((m % MOD) * (B2 % MOD)) % MOD;
            t2 = ((d % MOD) * (k % MOD)) % MOD;
            t2 = (t2 * sum_j) % MOD;
            part2 = (part2 - t2) % MOD;
            if(part2 < 0) part2 += MOD;
 
            ll add = (part1 * part2) % MOD;
            add = (add * mu[k]) % MOD;
            F_val = (F_val + add) % MOD;
            if(F_val < 0) F_val += MOD;
        }
        ll contrib = ((d - 1) % MOD * F_val) % MOD;
        S_nonAxis = (S_nonAxis + contrib) % MOD;
    }
    ll nonAxis = (2 * S_nonAxis) % MOD;
 
    // Total collinear triples are the sum of horizontal, vertical, and non-axis ones.
    ll collinear = (horiz + vert) % MOD;
    collinear = (collinear + nonAxis) % MOD;
 
    // Answer: non-degenerate triangles.
    ll ans = (totalTrip - collinear) % MOD;
    if(ans < 0) ans += MOD;
    cout << ans % MOD << "\n";
 
    return 0;
}
0