結果
問題 | No.890 移調の限られた旋法 |
ユーザー | ok |
提出日時 | 2019-09-21 01:13:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,664 bytes |
コンパイル時間 | 792 ms |
コンパイル使用メモリ | 81,268 KB |
実行使用メモリ | 20,864 KB |
最終ジャッジ日時 | 2024-09-15 06:32:09 |
合計ジャッジ時間 | 2,907 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
20,608 KB |
testcase_01 | AC | 26 ms
20,608 KB |
testcase_02 | AC | 25 ms
20,608 KB |
testcase_03 | AC | 25 ms
20,608 KB |
testcase_04 | AC | 25 ms
20,608 KB |
testcase_05 | AC | 24 ms
20,608 KB |
testcase_06 | AC | 24 ms
20,608 KB |
testcase_07 | AC | 24 ms
20,480 KB |
testcase_08 | AC | 24 ms
20,608 KB |
testcase_09 | AC | 25 ms
20,864 KB |
testcase_10 | AC | 24 ms
20,480 KB |
testcase_11 | AC | 25 ms
20,608 KB |
testcase_12 | AC | 25 ms
20,608 KB |
testcase_13 | AC | 50 ms
20,736 KB |
testcase_14 | AC | 37 ms
20,608 KB |
testcase_15 | AC | 37 ms
20,608 KB |
testcase_16 | AC | 49 ms
20,608 KB |
testcase_17 | AC | 39 ms
20,608 KB |
testcase_18 | AC | 46 ms
20,736 KB |
testcase_19 | AC | 37 ms
20,736 KB |
testcase_20 | AC | 29 ms
20,608 KB |
testcase_21 | AC | 26 ms
20,608 KB |
testcase_22 | AC | 34 ms
20,480 KB |
testcase_23 | AC | 35 ms
20,608 KB |
testcase_24 | AC | 31 ms
20,480 KB |
testcase_25 | AC | 27 ms
20,608 KB |
testcase_26 | AC | 38 ms
20,736 KB |
testcase_27 | AC | 38 ms
20,736 KB |
testcase_28 | AC | 33 ms
20,608 KB |
testcase_29 | AC | 31 ms
20,608 KB |
testcase_30 | AC | 37 ms
20,736 KB |
testcase_31 | AC | 38 ms
20,736 KB |
testcase_32 | AC | 47 ms
20,608 KB |
testcase_33 | AC | 46 ms
20,736 KB |
testcase_34 | AC | 46 ms
20,480 KB |
ソースコード
#include<iostream> #include<string> #include<iomanip> #include<cmath> #include<vector> #include<algorithm> using namespace std; #define int long long #define endl "\n" const long long INF = (long long)1e18; const long long MOD = 1'000'000'007; string yn(bool f){return f?"Yes":"No";} string YN(bool f){return f?"YES":"NO";} #define MAX_VAL 1100000 long long fac[MAX_VAL], mmi[MAX_VAL]; void factorial_mod(){ fac[0]=fac[1]=1; for(long long i = 2; i < MAX_VAL; fac[i]%=MOD,i++) fac[i] = fac[i-1]*(i%MOD); } long long power_mod(long long x, long long n){ long long ans = 1; for(;n;n>>=1,x*=x,ans%=MOD,x%=MOD) if(n&1)ans*=x; return ans%MOD; } void exgcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1; y = 0; return ; } exgcd(b,a%b,y,x); y -= a/b * x; } void modular_multiplicatibe_inverse(){ int x, y; exgcd(fac[MAX_VAL-1],MOD,x,y); mmi[MAX_VAL-1] = x; for(long long i = MAX_VAL-2; i >= 0; mmi[i]%=MOD,i--) mmi[i] = mmi[i+1]*((i+1)%MOD); } long long combination(long long n, long long r){ return n < r ? 0 :fac[n]*(mmi[r]*mmi[n-r]%MOD)%MOD; } signed main(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(10); const int MAX = 1100000; int N, K, Z = 1; int ans = 0; static int dp[MAX] = {}; cin>>N>>K; factorial_mod(); modular_multiplicatibe_inverse(); for(int i = 1; i < N; i++){ if(N%i == 0){ int x = N/i; if(K%x == 0) dp[i] = combination(i, K/x)%MOD; } } for(int i = 1; i < N; i++){ if(dp[i]){ ans += dp[i]; ans %= MOD; for(int j = i * 2; j <= N; j += i){ if(N%j == 0) dp[j] = (MOD - dp[i] + dp[j]) % MOD; } } } cout<<ans<<endl; return 0; }