結果

問題 No.890 移調の限られた旋法
ユーザー SalmonizeSalmonize
提出日時 2020-05-04 19:17:10
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,643 ms / 2,000 ms
コード長 620 bytes
コンパイル時間 351 ms
コンパイル使用メモリ 10,984 KB
実行使用メモリ 94,384 KB
最終ジャッジ日時 2023-09-07 02:24:01
合計ジャッジ時間 36,773 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 715 ms
86,372 KB
testcase_01 AC 685 ms
86,304 KB
testcase_02 AC 691 ms
86,312 KB
testcase_03 AC 686 ms
86,432 KB
testcase_04 AC 688 ms
86,368 KB
testcase_05 AC 713 ms
86,136 KB
testcase_06 AC 694 ms
86,472 KB
testcase_07 AC 689 ms
86,144 KB
testcase_08 AC 688 ms
86,392 KB
testcase_09 AC 702 ms
86,140 KB
testcase_10 AC 689 ms
86,320 KB
testcase_11 AC 685 ms
86,124 KB
testcase_12 AC 681 ms
86,492 KB
testcase_13 AC 1,400 ms
94,324 KB
testcase_14 AC 808 ms
94,384 KB
testcase_15 AC 1,168 ms
94,384 KB
testcase_16 AC 1,307 ms
94,320 KB
testcase_17 AC 1,270 ms
93,460 KB
testcase_18 AC 1,401 ms
93,480 KB
testcase_19 AC 948 ms
90,568 KB
testcase_20 AC 789 ms
89,168 KB
testcase_21 AC 721 ms
87,148 KB
testcase_22 AC 970 ms
92,620 KB
testcase_23 AC 895 ms
93,852 KB
testcase_24 AC 902 ms
90,632 KB
testcase_25 AC 724 ms
87,464 KB
testcase_26 AC 1,097 ms
93,964 KB
testcase_27 AC 1,028 ms
93,992 KB
testcase_28 AC 834 ms
91,148 KB
testcase_29 AC 832 ms
89,708 KB
testcase_30 AC 1,449 ms
93,468 KB
testcase_31 AC 997 ms
90,512 KB
testcase_32 AC 1,643 ms
93,012 KB
testcase_33 AC 1,509 ms
93,524 KB
testcase_34 AC 1,197 ms
93,276 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n_ = 10**6
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod

def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod
    
n, k = map(int, input().split())
res = [0]*(n+1)
for x in range(2,k+1):
    if n % x == k % x == 0:
        res[x] = nCr(n//x, k//x)
for i in range(n, 1, -1):
    if res[i]:
        for p in range(i*2, n+1, i):
            res[i] = (res[i] - res[p]) % mod
print(sum(res) % mod)
0