結果
問題 | No.890 移調の限られた旋法 |
ユーザー | dekomori_sanae |
提出日時 | 2022-02-19 16:48:41 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,939 bytes |
コンパイル時間 | 955 ms |
コンパイル使用メモリ | 94,568 KB |
実行使用メモリ | 50,304 KB |
最終ジャッジ日時 | 2024-06-29 10:28:20 |
合計ジャッジ時間 | 5,900 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
26,880 KB |
testcase_01 | AC | 44 ms
26,880 KB |
testcase_02 | AC | 45 ms
26,880 KB |
testcase_03 | AC | 44 ms
27,008 KB |
testcase_04 | AC | 44 ms
26,752 KB |
testcase_05 | AC | 46 ms
26,880 KB |
testcase_06 | WA | - |
testcase_07 | AC | 45 ms
27,008 KB |
testcase_08 | AC | 45 ms
26,880 KB |
testcase_09 | AC | 45 ms
26,880 KB |
testcase_10 | AC | 45 ms
26,880 KB |
testcase_11 | AC | 46 ms
26,880 KB |
testcase_12 | AC | 46 ms
26,880 KB |
testcase_13 | AC | 194 ms
50,048 KB |
testcase_14 | AC | 183 ms
50,048 KB |
testcase_15 | WA | - |
testcase_16 | AC | 177 ms
50,304 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 99 ms
39,040 KB |
testcase_20 | AC | 75 ms
34,560 KB |
testcase_21 | AC | 52 ms
28,288 KB |
testcase_22 | AC | 141 ms
44,672 KB |
testcase_23 | AC | 168 ms
48,640 KB |
testcase_24 | AC | 97 ms
39,296 KB |
testcase_25 | AC | 57 ms
29,696 KB |
testcase_26 | WA | - |
testcase_27 | AC | 178 ms
49,536 KB |
testcase_28 | AC | 119 ms
41,472 KB |
testcase_29 | AC | 85 ms
36,224 KB |
testcase_30 | AC | 168 ms
47,744 KB |
testcase_31 | AC | 97 ms
38,656 KB |
testcase_32 | AC | 165 ms
46,336 KB |
testcase_33 | WA | - |
testcase_34 | AC | 161 ms
47,488 KB |
ソースコード
#include <iostream> #include <cstdio> #include <string> #include <algorithm> #include <utility> #include <cmath> #include <vector> #include <stack> #include <queue> #include <deque> #include <set> #include <map> #include <tuple> #include <numeric> #include <functional> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef vector<vector<ll>> vvl; typedef pair<ll, ll> P; #define rep(i, n) for(ll i = 0; i < n; i++) #define exrep(i, a, b) for(ll i = a; i <= b; i++) #define out(x) cout << x << endl #define exout(x) printf("%.10f\n", x) #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define pb push_back #define re0 return 0 const ll mod = 1000000007; const ll INF = 1e16; struct Eratosthenes { vl isprime; // isprime[i] : iが素数なら1 vl minfactor; // minfactor[i] : iを割り切る最小の素数 vl mobius; // mobius[i] : メビウス関数 μ(i) Eratosthenes(ll n) : isprime(n+1, 1), minfactor(n+1, -1), mobius(n+1, 1) { isprime[1] = 0; minfactor[1] = 1; exrep(p, 2, n) { if(!isprime[p]) { continue; } minfactor[p] = p; mobius[p] = -1; for(ll q = 2*p; q <= n; q += p) { isprime[q] = 0; if(minfactor[q] == -1) { minfactor[q] = p; } if((q / p) % p == 0) { mobius[q] = 0; } else { mobius[q] = -mobius[q]; } } } } // 高速素因数分解。O(log(n))でnを素因数分解する vector<P> factorize(ll n) { // (素因数, 指数) のvectorを返す vector<P> res; while(n > 1) { ll p = minfactor[n]; ll i = 0; while(minfactor[n] == p) { n /= p; i++; } res.emplace_back(make_pair(p, i)); } return res; } // 高速約数列挙。O(σ(n))でnの約数を求める。σ(n)はnの約数の個数 vl divisors(ll n) { vl res({1}); auto pf = factorize(n); for(auto p : pf) { ll s = res.size(); rep(i, s) { ll x = 1; rep(j, p.second) { x *= p.first; res.pb(res[i] * x); } } } return res; } }; // nの約数を昇順に列挙したvectorを返す。計算量はO(√n) vector<ll> yakusu(ll n) { vl res; for(ll i = 1; i*i <= n; i++) { if(n % i == 0) { res.pb(i); if(i != n / i) { res.pb(n / i); } } } sort(all(res)); return res; } const ll MAX = 1000010; ll fact[MAX]; // fact[i] : iの階乗のmod ll inv[MAX]; // inv[i] : iの逆数のmod ll invfact[MAX]; // invfact[i] : iの階乗の逆数のmod void init() { fact[0] = 1; inv[0] = inv[1] = 1; invfact[0] = 1; for(ll i = 1; i < MAX; i++) { fact[i] = i * fact[i-1] % mod; if(i >= 2) { inv[i] = mod - inv[mod % i] * (mod / i) % mod; } invfact[i] = invfact[i-1] * inv[i] % mod; } } // nCrをO(n)で求める。 ll Comb(ll n, ll r) { if(r < 0 || n < 0 || n < r) { return 0; } ll res = fact[n]; res = (res * invfact[r]) % mod; res = (res * invfact[n - r]) % mod; return res; } int main() { ll n, k; cin >> n >> k; init(); vl v = yakusu(n); Eratosthenes e(n+1); ll ans = 0; for(ll i : v) { if(i == 1 || i == n || k % i != 0) { continue; } ans += -e.mobius[i] * Comb(n / i, k / i); ans %= mod; } out(ans); re0; }