結果

問題 No.1164 GCD Products hard
ユーザー dachengzdachengz
提出日時 2022-12-19 17:21:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 647 ms / 2,500 ms
コード長 1,209 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 138,176 KB
最終ジャッジ日時 2024-11-18 01:08:53
合計ジャッジ時間 10,972 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 318 ms
92,360 KB
testcase_01 AC 396 ms
96,740 KB
testcase_02 AC 322 ms
88,548 KB
testcase_03 AC 125 ms
73,036 KB
testcase_04 AC 171 ms
78,172 KB
testcase_05 AC 367 ms
93,620 KB
testcase_06 AC 503 ms
98,340 KB
testcase_07 AC 569 ms
100,548 KB
testcase_08 AC 622 ms
102,804 KB
testcase_09 AC 341 ms
90,216 KB
testcase_10 AC 107 ms
72,840 KB
testcase_11 AC 363 ms
90,884 KB
testcase_12 AC 474 ms
98,316 KB
testcase_13 AC 239 ms
87,176 KB
testcase_14 AC 640 ms
107,536 KB
testcase_15 AC 590 ms
103,800 KB
testcase_16 AC 647 ms
107,628 KB
testcase_17 AC 323 ms
92,020 KB
testcase_18 AC 306 ms
90,136 KB
testcase_19 AC 174 ms
81,508 KB
testcase_20 AC 183 ms
79,904 KB
testcase_21 AC 507 ms
101,756 KB
testcase_22 AC 32 ms
53,980 KB
testcase_23 AC 423 ms
138,176 KB
testcase_24 AC 558 ms
103,388 KB
testcase_25 AC 33 ms
52,484 KB
testcase_26 AC 31 ms
53,104 KB
testcase_27 AC 33 ms
53,184 KB
testcase_28 AC 32 ms
52,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

A, B, N = map(int, input().split())

mod = 10 ** 9 + 7
mod2 = 10 ** 9 + 6

A -= 1
B2 = B // 2
B21 = B2 + 1
L0 = max(A, B2)
L1 = L0 + 1
cnt = [0] * L1

ret = 1
for i in range(B, L0, -1):
    ret = ret * i % mod

lastBi = lastval = 0
tmpprod = 1
for i in range(L0, A, -1):
    Bi = B // i
    if Bi != lastBi:
        ret = ret * pow(tmpprod, lastval, mod) % mod
        tmpprod, lastBi = i, Bi
        lastval = pow(Bi, N, mod2)
        for n in range(i + i, B21, i):
            lastval -= cnt[n]
        lastval = (lastval - Bi + Bi // 2) % mod2
    else:
        tmpprod = tmpprod * i % mod
    cnt[i] = lastval
ret = ret * pow(tmpprod, lastval, mod) % mod

lastAi = lastBi = lastval = 0
tmpprod = 1
for i in range(A, 1, -1):
    Bi = B // i
    Ai = A // i
    if Ai == Bi:
        continue
    if Bi != lastBi or Ai != lastAi:
        ret = ret * pow(tmpprod, lastval, mod) % mod
        tmpprod, lastAi, lastBi = i, Ai, Bi
        lastval = pow(Bi - Ai, N, mod2)
        for n in range(i + i, L1, i):
            lastval -= cnt[n]
        lastval = (lastval - Bi + L0 // i) % mod2
    else:
        tmpprod = tmpprod * i % mod
    cnt[i] = lastval
ret = ret * pow(tmpprod, lastval, mod) % mod
print(ret)
0