結果

問題 No.1627 三角形の成立
ユーザー lam6er
提出日時 2025-04-09 20:56:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 197 ms / 1,000 ms
コード長 1,987 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 79,776 KB
最終ジャッジ日時 2025-04-09 20:58:01
合計ジャッジ時間 3,486 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def mobius(n_max):
    mu = [1] * (n_max + 1)
    is_prime = [True] * (n_max + 1)
    for p in range(2, n_max + 1):
        if is_prime[p]:
            for multiple in range(p, n_max + 1, p):
                is_prime[multiple] = False if multiple != p else is_prime[multiple]
                mu[multiple] *= -1
            p_square = p * p
            for multiple in range(p_square, n_max + 1, p_square):
                mu[multiple] = 0
    return mu

n, m = map(int, input().split())

def comb(a, r):
    if a < r:
        return 0
    inv6 = 166666668  # Modular inverse of 6 mod 1e9+7
    return a % MOD * (a - 1) % MOD * (a - 2) % MOD * inv6 % MOD

total_comb = comb(n * m, 3)

v_comb = n % MOD * comb(m, 3) % MOD
h_comb = m % MOD * comb(n, 3) % MOD

max_k = max(n, m)
mu = mobius(max_k)

diag_sum = 0
max_d = min(n-1, m-1)
inv2 = 500000004  # Modular inverse of 2 mod 1e9+7

for d in range(2, max_d + 1):
    A = (n - 1) // d
    B = (m - 1) // d
    if A == 0 or B == 0:
        continue
    res = 0
    K = max(A, B)
    for k in range(1, K + 1):
        if mu[k] == 0:
            continue
        x = A // k
        y = B // k
        if x == 0 or y == 0:
            continue
        term1 = (n % MOD) * (x % MOD) % MOD
        dk = (d % MOD) * (k % MOD) % MOD
        part1 = dk * (x % MOD) % MOD
        part1 = part1 * ((x + 1) % MOD) % MOD
        part1 = part1 * inv2 % MOD
        term1 = (term1 - part1) % MOD
        
        term2 = (m % MOD) * (y % MOD) % MOD
        part2 = dk * (y % MOD) % MOD
        part2 = part2 * ((y + 1) % MOD) % MOD
        part2 = part2 * inv2 % MOD
        term2 = (term2 - part2) % MOD
        
        contribution = term1 * term2 % MOD
        contribution = contribution * mu[k] % MOD
        res = (res + contribution) % MOD
    res = res * (d - 1) % MOD
    diag_sum = (diag_sum + res) % MOD

diag_sum = diag_sum * 2 % MOD

ans = (total_comb - v_comb - h_comb - diag_sum) % MOD
ans = (ans + MOD) % MOD

print(ans)
0