結果
問題 | No.1581 Multiple Sequence |
ユーザー |
|
提出日時 | 2021-07-03 22:23:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 7,312 ms |
コンパイル使用メモリ | 309,996 KB |
最終ジャッジ日時 | 2025-01-22 17:20:52 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#define _GLIBCXX_DEBUG #include<bits/stdc++.h> #include <atcoder/all> #define rep(i,n) for(long long i = 0;i < (n);i++) #define all(v) v.begin(),v.end() #define dec(n) cout << fixed << setprecision(n); #define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ" #define small "abcdefghijklmnopqrstuvwxyz" using namespace std; using namespace atcoder; using ll = long long; using P = pair<ll,ll>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; const ll MOD = 1000000007; const ll MAX = 2000100; const ll inf = 8e18; const long double pi = acos(-1); ll gcd(ll a,ll b){ if(b == 0) return a; return gcd(b , a % b); } ll mod(ll a){ return a % MOD; } ll lcm(ll a,ll b){ return (a*b)/gcd(a,b); } ll memo[100009]; ll iscame[100009]; ll dp(ll x){ if(iscame[x]) return memo[x]; iscame[x] = true; ll ans = 0; for(ll i=1; i*i <= x; i++){ if(i == 1){ ans += 1; ans += dp(x-1); continue; } if(x % i == 0){ if(i*i == x){ ans += dp((x-i)/i); ans %= MOD; } else{ ans += dp((x-(x/i))/(x/i)); ans += dp((x-i)/i); ans %= MOD; } } } return memo[x] = ans; } int main(){ ll m; cin >> m; memo[0] = 0; iscame[0] = true; memo[1] = 1; iscame[1] = true; cout << dp(m) << endl; // rep(i,m+1) cout << dp(i) << ' '; }