結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:18:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,505 bytes |
コンパイル時間 | 2,160 ms |
コンパイル使用メモリ | 178,896 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-09-14 18:05:31 |
合計ジャッジ時間 | 3,698 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 100000000long long gcd(long long a, long long b){if (b == 0) return a;return gcd(b, a % b);}//aのb乗int beki(int a,int b){int x = 1;while(b!=0){if(b&1){x=mod(x*a);}a=mod(a*a);b>>=1;}return x;}//aの逆元int gyakugen(int a){return beki(a,modulo-2);}struct combi{deque<int> kaijou;deque<int> kaijou_;void kaijou_set(int n){kaijou.push_back(1);for(int i=1;i<=n;i++){kaijou.push_back(mod(kaijou[i-1]*i));}int b=gyakugen(kaijou[n]);kaijou_.push_front(b);for(int i=1;i<=n;i++){int k=n+1-i;kaijou_.push_front(mod(kaijou_[0]*k));}}int combination(int n,int r){if(r>n)return 0;int a = mod(kaijou[n]*kaijou_[r]);a=mod(a*kaijou_[n-r]);return a;}int junretsu(int a,int b){int x = mod(kaijou_[a]*kaijou_[b]);x=mod(x*kaijou[a+b]);return x;}};int main(){int N,K;cin>>N>>K;combi C;C.kaijou_set(N+2);int ans = 0;//set<pair<int,int>> S;map<int,int> S;for(int i=2;i<=N;i++){if(N%i==0&&K%i==0){int a = N/i;int b = K/i;int cnt = 1;for(auto X:S){if(X.first%a==0){cnt -= X.second;}}//cout<<C.combination(a,b)<<endl;ans = mod(ans + mod(cnt*C.combination(a,b)));S[a] = cnt;//S.insert(a);//S.insert({a/gcd(a,b),b/gcd(a,b)});}}cout<<ans<<endl;return 0;}