結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:06:15 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,439 bytes |
コンパイル時間 | 683 ms |
コンパイル使用メモリ | 65,944 KB |
実行使用メモリ | 201,524 KB |
最終ジャッジ日時 | 2024-09-14 17:47:43 |
合計ジャッジ時間 | 72,765 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 TLE * 1 |
other | AC * 17 TLE * 15 |
ソースコード
#include <iostream>#include <map>#include <vector>#define llint long long#define mod 1000000007using namespace std;const int FACT_MAX = 1000005;llint fact[FACT_MAX], fact_inv[FACT_MAX];llint modpow(llint a, llint n){if(n == 0) return 1;if(n % 2){return ((a%mod) * (modpow(a, n-1)%mod)) % mod;}else{return modpow((a*a)%mod, n/2) % mod;}}void make_fact(){llint val = 1;fact[0] = 1;for(int i = 1; i < FACT_MAX; i++){val *= i;val %= mod;fact[i] = val;}fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);for(int i = FACT_MAX-2; i >= 0; i--){fact_inv[i] = fact_inv[i+1] * (i+1) % mod;}}llint comb(llint n, llint k){llint ret = 1;ret *= fact[n];ret *= fact_inv[k], ret %= mod;ret *= fact_inv[n-k], ret %= mod;return ret;}llint gcd(llint a, llint b){if(b == 0) return a;return gcd(b, a%b);}llint n, k;vector<llint> vec[1000005];;llint dp[1000005];int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;make_fact();for(int i = 1; i <= 1000000; i++){for(int j = 2; i*j <= 1000000; j++){vec[i*j].push_back(i);}}for(int i = 1; i <= n; i++){if(n % i) continue;if(k % (n/i)) continue;dp[i] = comb(i, k/(n/i));for(int j = 0; j < vec[i].size(); j++){dp[i] += mod - dp[vec[i][j]], dp[i] %= mod;}}llint ans = 0;for(int i = 1; i < n; i++) ans += dp[i], ans %= mod;cout << ans << endl;return 0;}