結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:06:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 1,790 bytes |
コンパイル時間 | 1,034 ms |
コンパイル使用メモリ | 103,548 KB |
実行使用メモリ | 38,400 KB |
最終ジャッジ日時 | 2024-09-14 17:43:19 |
合計ジャッジ時間 | 3,429 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<iostream>#include<string>#include<algorithm>#include<vector>#include<iomanip>#include<math.h>#include<complex>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#include<bitset>#include<functional>#include<assert.h>#include<numeric>using namespace std;#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)using ll = long long;const int inf=1e9+7;const ll longinf=1LL<<60 ;const ll mod=1e9+7 ;vector<ll> inv,fact,invfact;void mod_build(int n=101010){fact.resize(n+1);inv.resize(n+1);invfact.resize(n+1);fact[0]=inv[0]=invfact[0]=1;inv[1]=1;rep(i,n){fact[i+1]=fact[i]*(i+1)%mod;if(i>0)inv[i+1]=mod-inv[mod%(i+1)]*(mod/(i+1))%mod;invfact[i+1]=invfact[i]*inv[i+1]%mod;}}ll perm(int n,int k){if(n<0||k<0||k>n)return 0;return fact[n]*invfact[n-k]%mod;}ll comb(int n,int k){if(n<0||k<0||k>n)return 0;return (fact[n]*invfact[n-k]%mod)*invfact[k]%mod;}ll powmod(ll n,ll k){k%=mod-1;if(k<0)k+=mod-1;ll ret=1;while(k){if(k&1)ret=ret*n%mod;n=n*n%mod;k>>=1;}return ret;}ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}int main(){int n,k;cin>>n>>k;int g = gcd(n,k);mod_build(n+5);vector<ll> res(n+1);REP(i,1,n+1){if(k%i==0&&n%i==0){res[n/i]=comb(n/i,k/i);}}vector<int> used(n+1,false);used[0]=used[1]=1;rep(i,n+1){if(used[i])continue;for(int j = 2*i;j<=n;j+=i){used[j]=1;}for(int j = n/i;j>=1;j--){res[i*j]+=mod-res[j];res[i*j]%=mod;}}cout<<(comb(n,k)-res[n]+mod)%mod<<endl;return 0;}