結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 21:56:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 1,892 bytes |
コンパイル時間 | 1,250 ms |
コンパイル使用メモリ | 118,356 KB |
実行使用メモリ | 27,136 KB |
最終ジャッジ日時 | 2024-09-14 17:25:49 |
合計ジャッジ時間 | 4,462 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <climits>#include <cmath>#include <complex>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>#include <vector>#include <cstdint>using namespace std;typedef long long ll;#define MP make_pair#define PB push_back#define inf 1000000007#define mod 1000000007#define rep(i,n) for(int i = 0; i < (int)(n); ++i)template<typename T>vector<T> divisor(T n){vector<T> res;for(T i=1;(long long)i*i<=n;i++){if(n%i==0){res.push_back(i);if(i != n/i){res.push_back(n/i);}}}sort(res.rbegin(),res.rend());return res;}#define MAX_N 2000010#define MOD 1000000007int inv[MAX_N],fac[MAX_N],finv[MAX_N];void make(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for(int i=2;i<MAX_N;i++){inv[i] = MOD - (long long)inv[MOD%i] * (MOD/i) % MOD;fac[i] = (long long)fac[i-1] * i % MOD;finv[i] = (long long)finv[i-1] * inv[i] % MOD;}}int comb(int a,int b){if(a < b){return 0;}return fac[a] * ((long long)finv[b] * finv[a-b] % MOD) % MOD;}ll dp[2000000]={};int main(){make();int n,k;cin >> n >> k;vector<int> res = divisor(n);ll sm = 0;for(int x:res){if(x==1)continue;if(k%x==0){int c = k/x;int p = n/x;dp[x] = comb(p,c);for(int i=x+x;i<=n;i+=x){dp[x] += mod-dp[i];dp[x] %= mod;}sm += dp[x];sm %= mod;}}cout << sm << endl;return 0;}