結果

問題 No.886 Direct
ユーザー lam6er
提出日時 2025-03-20 20:53:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 477 ms / 4,000 ms
コード長 1,492 bytes
コンパイル時間 234 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 123,248 KB
最終ジャッジ日時 2025-03-20 20:53:45
合計ジャッジ時間 7,237 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    H, W = map(int, input().split())
    
    X = H - 1
    Y = W - 1
    
    if X < 0:
        X = 0
    if Y < 0:
        Y = 0
    
    max_d = max(X, Y) if X > 0 or Y > 0 else 0
    mu = [1] * (max_d + 1) if max_d != 0 else []
    is_prime = [True] * (max_d + 1) if max_d != 0 else []
    
    if max_d >= 2:
        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]
                    mu[multiple] *= -1
                p_square = p * p
                for multiple in range(p_square, max_d + 1, p_square):
                    mu[multiple] = 0
    
    horizontal = (H - 1) * W % MOD if H >= 1 else 0
    vertical = H * (W - 1) % MOD if W >= 1 else 0
    diagonal = 0
    
    if X > 0 and Y > 0:
        for d in range(1, X + 1):
            if mu[d] == 0:
                continue
            m = Y // d
            if m == 0:
                continue
            term_d = mu[d] * ((Y + 1) * m - d * m * (m + 1) // 2)
            term_d %= MOD
            k_max = X // d
            sum_k = ( (X + 1) * k_max - d * k_max * (k_max + 1) // 2 ) % MOD
            contribution = (term_d * sum_k) % MOD
            diagonal = (diagonal + contribution) % MOD
        diagonal = (2 * diagonal) % MOD
    
    ans = (horizontal + vertical + diagonal) % MOD
    print(ans)

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