結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2020-06-15 21:26:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 31 ms / 2,000 ms |
コード長 | 3,415 bytes |
コンパイル時間 | 1,495 ms |
コンパイル使用メモリ | 171,400 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-07-03 11:33:34 |
合計ジャッジ時間 | 2,848 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>#define debug(x) cerr << #x << ": " << x << endl#define debugArray(x, n) \for (long long hoge = 0; (hoge) < (n); ++(hoge)) \cerr << #x << "[" << hoge << "]: " << x[hoge] << endlusing namespace std;template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod)) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) { return *this *= p.inverse(); }ModInt operator-() const { return ModInt() - *this; }ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }bool operator==(const ModInt &p) const { return x == p.x; }bool operator!=(const ModInt &p) const { return x != p.x; }ModInt inverse() const {int a = x, b = mod, u = 1, v = 0, t;while (b) t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);return ModInt(u);}ModInt pow(int64_t e) const {ModInt ret(1);for (ModInt b = *this; e; e >>= 1, b *= b)if (e & 1) ret *= b;return ret;}friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }friend istream &operator>>(istream &is, ModInt &a) {int64_t t;is >> t;a = ModInt<mod>(t);return (is);}static int modulo() { return mod; }};template <class Modint>struct Combination {static vector<Modint> _fact, _finv, _inv;static void init(int sz) {int n = min(sz, Modint::modulo() - 1);_fact.resize(n + 1), _finv.resize(n + 1), _inv.resize(n + 1);for (int i = 0; i <= n; ++i) _fact[i] = i ? Modint(i) * _fact[i - 1] : 1;_finv[n] = _fact[n].inverse();for (int i = n; i; --i) _finv[i - 1] = Modint(i) * _finv[i];for (int i = 1; i <= n; ++i) _inv[i] = _finv[i] * _fact[i - 1];}static Modint inverse(int n) { return _inv[n]; }static Modint fact(int n, bool inv = 0) { return inv ? _finv[n] : _fact[n]; }static Modint nPr(int n, int r) {if (n < r || r < 0) return Modint(0);return _fact[n] * _finv[n - r];}static Modint nCr(int n, int r) { return nPr(n, r) * _finv[r]; }static Modint nHr(int n, int r) { return !r ? Modint(1) : nCr(n + r - 1, r); }static size_t size() { return _inv.size(); }};template <class Modint>vector<Modint> Combination<Modint>::_fact;template <class Modint>vector<Modint> Combination<Modint>::_finv;template <class Modint>vector<Modint> Combination<Modint>::_inv;signed main() {cin.tie(0);ios::sync_with_stdio(false);using Mint = ModInt<int(1e9 + 7)>;using Comb = Combination<Mint>;int N, K;cin >> N >> K;Comb::init(N);Mint dp[N];fill(dp, dp + N, 0);Mint ans = 0;for (int i = 1; i < N; i++)if (N % i == 0) {int P = N / i;if (K % P == 0) {dp[i] += Comb::nCr(i, K / P);ans += dp[i];for (int j = 2 * i; j < N; j += i) dp[j] -= dp[i];}}cout << ans << endl;return 0;}