結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2020-03-26 22:30:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 2,296 bytes |
コンパイル時間 | 1,402 ms |
コンパイル使用メモリ | 165,136 KB |
実行使用メモリ | 46,240 KB |
最終ジャッジ日時 | 2025-01-02 07:12:30 |
合計ジャッジ時間 | 4,188 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) x.begin(),x.end()#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define INF 1000000000#define mod 1000000007using ll=long long;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0};int dy[]={0,1,0,-1};ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}const int MAX=1500000;long long fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % mod;//???inv[i] = mod - inv[mod%i] * (mod / i) % mod;finv[i] = finv[i - 1] * inv[i] % mod;}}// 二項係数計算long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % mod) % mod;}//n!ll fact_mod(ll n) {ll ret=1;for(ll i=2;i<=n;i++) ret=ret*(i%mod)%mod;return ret;}// 繰り返し二乗法ll pow_mod(ll x, ll n){if(n==0) return 1;ll ret=pow_mod((x*x) % mod, n/2);if(n&1) ret=(ret*x)%mod;return ret;}//nCr O(r) nがでかくても安心ll combination_mod(ll n, ll r) {if(r>n-r) r=n-r;if(r==0) return 1;ll a=1;//a=n!/(n-r)!=n~n-r+1までの総積->O(r)for(ll i=0;i<r;i++) a=a*((n-i)%mod)%mod;//b=inv(r!)ll b=pow_mod(fact_mod(r), mod-2);return (a%mod)*(b%mod)%mod;}ll inv_mod(ll n){// フェルマーの小定理return pow_mod(n,mod-2);}signed main(){cin.tie(0);ios::sync_with_stdio(0);COMinit();ll n,k;cin>>n>>k;vector<ll> dp(n+1,0);for(int i=1;i<n;i++)if(n%i==0){int t=n/i;//t個に分割if(k%t==0) dp[i]=COM(i,k/t);}ll ans=0;for(int i=1;i<n;i++)if(n%i==0){int t=n/i;if(k%t==0){ans+=dp[i];ans%=mod;for(int j=i+i;j<n;j+=i){dp[j]+=mod-dp[i];dp[j]%=mod;}}}cout<<ans<<endl;return 0;}