結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:30:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 3,349 bytes |
コンパイル時間 | 1,349 ms |
コンパイル使用メモリ | 121,260 KB |
実行使用メモリ | 21,376 KB |
最終ジャッジ日時 | 2024-09-14 18:23:38 |
合計ジャッジ時間 | 3,284 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include<iostream>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<cassert>#include<complex>using namespace std;//#define int long longtypedef long long ll;typedef unsigned long long ul;typedef unsigned int ui;const ll mod = 1000000007;const ll INF = mod * mod;typedef pair<int, int>P;typedef pair<int, bool> sP;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef pair<ll, ll> LP;typedef vector<ll> vec;typedef long double ld;typedef pair<ld, ld> LDP;const ld eps = 1e-5;const ld pi = acos(-1.0);typedef vector<vector<ll>> mat;typedef vector<ll> vec;ll mod_pow(ll x, ll n) {ll ret = 1;while (n > 0) {if (n % 2)ret = ret * x%mod;x = x * x%mod; n >>= 1;}return ret;}struct perm {private:int sz;vector<ll> p, invp;public:perm(int n) {sz = n + 1;p.resize(sz), invp.resize(sz);p[0] = 1;rep1(i, sz - 1) {p[i] = p[i - 1] * i%mod;}invp[sz - 1] = 1;ll cop = mod - 2, x = p[sz - 1];while (cop) {if (cop % 2)invp[sz - 1] = invp[sz - 1] * x%mod;cop >>= 1; x = x * x % mod;}per(i, sz - 1) {invp[i] = invp[i + 1] * (i + 1) % mod;}}ll comb(ll x, ll y) {if (x < y || y < 0)return 0;ll ret = p[x];(ret *= invp[y]) %= mod;(ret *= invp[x - y]) %= mod;return ret;}ll combP(ll x, ll y) {if (x < y || y < 0)return 0;return p[x] * invp[x - y] % mod;}};bool isp[1 << 20];//vector<int> ch[1 << 20];vector<int> tempura0224;void init() {fill(isp + 2, isp + (1 << 20), true);for (int j = 2; j < (1 << 20); j++) {if (!isp[j])continue;tempura0224.push_back(j);//ch[j].push_back(j);for (int i = 2 * j; i < (1 << 20); i += j) {//ch[i].push_back(j);isp[i] = false;}}}perm p(1 << 20);ll cnt[1 << 20];void solve() {int n, k; cin >> n >> k;int d = sqrt(n + 0.1);vector<int> v;rep1(i, d) {if (n%i == 0) {v.push_back(i);v.push_back(n / i);}}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end()); v.pop_back();ll ans = 0;rep(i, v.size()) {ll d = v[i];int r = n / d;if (k%r != 0)continue;cnt[d] = p.comb(d, d*k / n);ll num = 0;vector<int> u;rep(j, tempura0224.size()) {if (tempura0224[j] > d)break;if (d%tempura0224[j] == 0) {u.push_back(tempura0224[j]);}}int len = u.size();rep(j, (1 << len)) {ll pro = 1;int id = 0;rep(k, len) {if (j & (1 << k)) {pro = pro*u[k];id ^= 1;}}if (id) {if (k*d / pro % n != 0)continue;num -= p.comb(d / pro, d*k / (n*pro));}else {if (k*d / pro % n != 0)continue;num += p.comb(d / pro, d*k / (n*pro));}}cnt[d] = (num%mod+mod)%mod;//cout << d << " " << cnt[d] << endl;}rep(i, (1 << 20))ans += cnt[i];cout << ans % mod << endl;}signed main() {ios::sync_with_stdio(false);cin.tie(0);init();solve();//stopreturn 0;}