結果
問題 | No.1581 Multiple Sequence |
ユーザー |
![]() |
提出日時 | 2021-07-02 22:57:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,799 bytes |
コンパイル時間 | 4,723 ms |
コンパイル使用メモリ | 255,112 KB |
最終ジャッジ日時 | 2025-01-22 16:43:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;#define rep(i,n)for (int i = 0; i < int(n); ++i)#define rrep(i,n)for (int i = int(n)-1; i >= 0; --i)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()template<class T> void chmax(T& a, const T& b) {a = max(a, b);}template<class T> void chmin(T& a, const T& b) {a = min(a, b);}using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using mint = modint1000000007;std::pair<std::vector<int>,std::vector<int>> primes_lpf(const int n) {std::pair<std::vector<int>,std::vector<int>> rv;std::vector<int>& primes = rv.first;std::vector<int>& lpf = rv.second;primes.reserve(n / 10);lpf.resize(n + 1);for(int i = 2; i <= n; i += 2) lpf[i] = 2;for(int i = 3; i <= n; i += 6) lpf[i] = 3;if (2 <= n) primes.push_back(2);if (3 <= n) primes.push_back(3);// 5 * x <= n, x <= floor(n / 5)const int n5 = n / 5;int x = 5;bool one_mod6 = false;// x_1 <= n5, x_2 = x_1 + 2 <= n5 + 2 <= nfor(; x <= n5; one_mod6 = !one_mod6, x += (one_mod6 ? 2 : 4)) {if (lpf[x] == 0) {lpf[x] = x;primes.push_back(x);}int px = lpf[x];for(int i = 2;; ++i) {int q = primes[i];int y = q * x;if (y > n) break;lpf[y] = q;if (q == px) break;}}for(; x <= n; one_mod6 = !one_mod6, x += (one_mod6 ? 2 : 4)) {if (lpf[x] == 0) {lpf[x] = x;primes.push_back(x);}}return rv;}auto [primes, lpf] = primes_lpf(1000000);std::vector<std::pair<int,int>> factorize(int n) {std::vector<std::pair<int,int>> fs;while(n > 1) {int p = lpf[n];int cnt = 0;do {n /= p; cnt++;} while(n % p == 0);fs.emplace_back(p, cnt);}return fs;}vector<int> divisors(int n) {assert(n >= 1);vector<int> ret{1};while(n > 1) {int p = lpf[n];int cnt = 0;do {n /= p; cnt++;} while(n % p == 0);int sz = ret.size();for(int q = 1, c = 1; c <= cnt; c++) {q *= p;for(int i = 0; i < sz; i++) ret.push_back(ret[i] * q);}}return ret;}mint memo[100001];bool valid[100001];mint f(int rest) {if (rest == 0) return 1;if (valid[rest]) return memo[rest];mint ret;for(int d: divisors(rest)) {ret += f(d - 1);}valid[rest] = true;return memo[rest] = ret;}int main() {ios::sync_with_stdio(false);cin.tie(0);int m;cin >> m;mint ans = f(m);cout << ans.val() << endl;}