結果
問題 | No.890 移調の限られた旋法 |
ユーザー | trineutron |
提出日時 | 2019-06-25 08:26:55 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 438 ms / 2,000 ms |
コード長 | 888 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 10,868 KB |
実行使用メモリ | 9,220 KB |
最終ジャッジ日時 | 2023-09-21 04:15:43 |
合計ジャッジ時間 | 5,154 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 21 ms
9,072 KB |
testcase_01 | AC | 21 ms
8,860 KB |
testcase_02 | AC | 21 ms
9,068 KB |
testcase_03 | AC | 21 ms
8,992 KB |
testcase_04 | AC | 21 ms
8,972 KB |
testcase_05 | AC | 21 ms
8,776 KB |
testcase_06 | AC | 21 ms
9,124 KB |
testcase_07 | AC | 21 ms
8,764 KB |
testcase_08 | AC | 21 ms
8,892 KB |
testcase_09 | AC | 21 ms
8,976 KB |
testcase_10 | AC | 20 ms
8,768 KB |
testcase_11 | AC | 21 ms
8,920 KB |
testcase_12 | AC | 21 ms
9,220 KB |
testcase_13 | AC | 184 ms
9,176 KB |
testcase_14 | AC | 21 ms
8,868 KB |
testcase_15 | AC | 182 ms
8,988 KB |
testcase_16 | AC | 181 ms
9,064 KB |
testcase_17 | AC | 165 ms
9,132 KB |
testcase_18 | AC | 274 ms
9,096 KB |
testcase_19 | AC | 74 ms
9,120 KB |
testcase_20 | AC | 21 ms
8,740 KB |
testcase_21 | AC | 21 ms
8,740 KB |
testcase_22 | AC | 97 ms
9,100 KB |
testcase_23 | AC | 20 ms
8,748 KB |
testcase_24 | AC | 75 ms
8,960 KB |
testcase_25 | AC | 21 ms
8,776 KB |
testcase_26 | AC | 215 ms
9,124 KB |
testcase_27 | AC | 60 ms
9,028 KB |
testcase_28 | AC | 21 ms
8,816 KB |
testcase_29 | AC | 62 ms
9,100 KB |
testcase_30 | AC | 423 ms
9,060 KB |
testcase_31 | AC | 154 ms
9,028 KB |
testcase_32 | AC | 356 ms
9,060 KB |
testcase_33 | AC | 438 ms
9,136 KB |
testcase_34 | AC | 233 ms
8,972 KB |
ソースコード
import math from itertools import combinations import functools import operator n, k = map(int, input().split()) pf=[] p_i=0 m=math.gcd(n, k) for i in range(2,int(m**0.5)+1): if m%i==0: pf.append(i) p_i+=1 while m%i==0: m//=i if m>1:pf.append(m) def framod(n, mod, a=1): for i in range(1,n+1): a=a * i % mod return a def power(n, r, mod): if r == 0: return 1 if r%2 == 0: return power(n*n % mod, r//2, mod) % mod if r%2 == 1: return n * power(n, r-1, mod) % mod def comb(n, k, mod): a=framod(n, mod) b=framod(k, mod) c=framod(n-k, mod) return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod mod=10**9+7 s=0 for r in range(len(pf)): for i in combinations(pf, r+1): p=functools.reduce(operator.mul,list(i)) s+=(-1)**r*comb(n//p, k//p, mod) s%=mod print(s)