結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
|
提出日時 | 2021-12-20 16:52:49 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,431 bytes |
コンパイル時間 | 3,284 ms |
コンパイル使用メモリ | 256,476 KB |
実行使用メモリ | 19,968 KB |
最終ジャッジ日時 | 2024-09-15 15:19:34 |
合計ジャッジ時間 | 4,935 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<bits/stdc++.h>#define mod 1000000007using namespace std;long long power(long long a,long long b){long long x=1,y=a;while(b>0){if(b&1ll){x=(x*y)%mod;}y=(y*y)%mod;b>>=1;}return x%mod;}long long modular_inverse(long long n){return power(n,mod-2);}long long factorial[1048576];long long invfact[1048576];void cfact(){long long i;factorial[0]=1;factorial[1]=1;for(i=2;i<1048576;i++){factorial[i]=factorial[i-1]*i;factorial[i]%=mod;}invfact[1048575]=modular_inverse(factorial[1048575]);for(i=1048574;i>=0;i--){invfact[i]=invfact[i+1]*(i+1);invfact[i]%=mod;}}long long calcnCr(long long n,long long k){if(k<0 || n<k){return 0;}return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;}int main(){cfact();ios::sync_with_stdio(false);cin.tie(nullptr);int n,k;cin >> n >> k;map<int,long long> mp;vector<int> mem;for(int i=1;i*i<=n;i++){if(n%i){continue;}mem.push_back(i);if(i*i!=n){mem.push_back(n/i);}}sort(mem.begin(),mem.end());mem.pop_back();long long res=0;for(auto &nx : mem){int num=n/nx;if(k%num){continue;}int sing=k/num;long long cur=calcnCr(nx,sing);for(auto &ny : mp){if(nx%ny.first==0){cur+=(mod-ny.second);cur%=mod;}}mp[nx]=cur;res+=cur;res%=mod;}cout << res << '\n';return 0;}