結果

問題 No.1164 GCD Products hard
ユーザー lam6er
提出日時 2025-04-15 21:49:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,898 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 360,020 KB
最終ジャッジ日時 2025-04-15 21:51:14
合計ジャッジ時間 7,776 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7
MOD_MINUS_1 = MOD - 1

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    A = int(data[0])
    B = int(data[1])
    N = int(data[2])
    
    max_num = B
    if max_num == 0:
        print(0)
        return
    
    # Compute Möbius function
    mu = [1] * (max_num + 1)
    is_prime = [True] * (max_num + 1)
    for p in range(2, max_num + 1):
        if is_prime[p]:
            for multiple in range(p, max_num + 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_num + 1, p_square):
                mu[multiple] = 0
    
    # Precompute cnt[x] for all x
    cnt = [0] * (max_num + 1)
    for x in range(1, max_num + 1):
        cnt[x] = (B // x) - ((A - 1) // x)
    
    # Precompute term[x] = pow(cnt[x], N, MOD_MINUS_1)
    term = [0] * (max_num + 1)
    for x in range(1, max_num + 1):
        c = cnt[x]
        if c <= 0:
            term[x] = 0
        else:
            term[x] = pow(c, N, MOD_MINUS_1)
    
    # Precompute S[k] = sum_{m=1 to M} term[k*m], where M = B // k
    S = [0] * (max_num + 1)
    for k in range(1, max_num + 1):
        if k > B:
            S[k] = 0
            continue
        M = B // k
        if M == 0:
            S[k] = 0
            continue
        total = 0
        for m in range(1, M + 1):
            x = k * m
            total += term[x]
            if total >= MOD_MINUS_1:
                total -= MOD_MINUS_1
        S[k] = total % MOD_MINUS_1
    
    # Compute the result
    result = 1
    for k in range(1, max_num + 1):
        if mu[k] == 0:
            continue
        exponent = (-mu[k] * S[k]) % MOD_MINUS_1
        result = (result * pow(k, exponent, MOD)) % MOD
    
    print(result)

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