結果

問題 No.1627 三角形の成立
ユーザー lam6er
提出日時 2025-03-26 15:59:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 178 ms / 1,000 ms
コード長 2,110 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 79,316 KB
最終ジャッジ日時 2025-03-26 16:00:15
合計ジャッジ時間 3,541 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

MOD = 10**9 + 7

def main():
    n, m = map(int, sys.stdin.readline().split())
    if n < 1 or m < 1:
        print(0)
        return
    
    # Precompute Mobius function
    max_d = max(n-1, m-1)
    mobius = [1] * (max_d + 1)
    is_prime = [True] * (max_d + 1)
    for p in range(2, max_d + 1):
        if is_prime[p]:
            for multiple in range(p, max_d + 1, p):
                is_prime[multiple] = False if multiple != p else is_prime[multiple]
                mobius[multiple] *= -1
            p_square = p * p
            for multiple in range(p_square, max_d + 1, p_square):
                mobius[multiple] = 0
    
    total = 0
    if n*m < 3:
        print(0)
        return
    total = (n * m) * (n * m -1) * (n * m -2) // 6 % MOD
    
    # Subtract horizontal lines
    if m >= 3:
        h = n * (m * (m-1) * (m-2) // 6) % MOD
        total = (total - h) % MOD
    
    # Subtract vertical lines
    if n >= 3:
        v = m * (n * (n-1) * (n-2) // 6) % MOD
        total = (total - v) % MOD
    
    # Subtract diagonal lines
    diagonal = 0
    max_d = min(n-1, m-1)
    for d in range(2, max_d + 1):
        A = (n-1) // d
        B = (m-1) // d
        if A == 0 or B == 0:
            continue
        current = 0
        max_k = max(A, B)
        for k in range(1, max_k + 1):
            mu = mobius[k]
            if mu == 0:
                continue
            Ak = A // k
            Bk = B // k
            if Ak == 0 or Bk == 0:
                continue
            term = (
                n * m * Ak * Bk % MOD
                - d * m * k * Ak * (Ak + 1) // 2 * Bk % MOD
                - d * n * k * Bk * (Bk + 1) // 2 * Ak % MOD
                + d * d * k * k * (Ak * (Ak + 1) // 2) % MOD * (Bk * (Bk + 1) // 2) % MOD
            ) % MOD
            term = term * mu % MOD
            current = (current + term) % MOD
        factor = (d - 1) * current % MOD
        diagonal = (diagonal + factor) % MOD
    
    diagonal = diagonal * 2 % MOD
    total = (total - diagonal) % MOD
    print(total % MOD)

if __name__ == '__main__':
    main()
0