結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 21:36:52 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,275 bytes |
コンパイル時間 | 803 ms |
コンパイル使用メモリ | 98,004 KB |
実行使用メモリ | 26,880 KB |
最終ジャッジ日時 | 2024-09-14 16:47:56 |
合計ジャッジ時間 | 2,680 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#define popcount __builtin_popcountusing namespace std;typedef long long ll;typedef pair<int, int> P;const ll MOD=1e9+7;ll powmod(ll a, ll k){ll ap=a, ans=1;while(k){if(k&1){ans*=ap;ans%=MOD;}ap=ap*ap;ap%=MOD;k>>=1;}return ans;}ll inv(ll a){return powmod(a, MOD-2);}ll f[5000001], invf[5000001];void fac(int n){f[0]=1;for(ll i=1; i<=n; i++) f[i]=f[i-1]*i%MOD;invf[n]=inv(f[n]);for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1)%MOD;}ll comb(int x, int y){if(!(0<=y && y<=x)) return 0;return f[x]*invf[y]%MOD*invf[x-y]%MOD;}int main(){ll n, k; cin>>n>>k;fac(n);ll c[1000010]={};ll ans=0;for(int i=k; i>=2; i--){if(n%i!=0 || k%i!=0) continue;c[i]=comb(n/i, k/i);for(int j=2*i; j<=k; j+=i){c[i]+=MOD-c[j];c[i]%=MOD;}(ans+=c[i])%=MOD;}cout<<ans<<endl;return 0;}