diff options
| -rw-r--r-- | 2020/US Open/Gold/exercise.cpp | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/2020/US Open/Gold/exercise.cpp b/2020/US Open/Gold/exercise.cpp new file mode 100644 index 0000000..7e8ba80 --- /dev/null +++ b/2020/US Open/Gold/exercise.cpp @@ -0,0 +1,35 @@ +#include <bits/stdc++.h> +using namespace std; +typedef long long ll; + +int sieve_size; +bitset<10000001> bs; +vector<int> pr; + +void sieve(int size) { + sieve_size = size; + bs.set(); bs[0] = bs[1] = 0; + for (ll i = 2; i <= sieve_size; ++i) if (bs[i]) { + for (ll j = i * i; j <= sieve_size; j += i) bs[j] = 0; + pr.push_back(i); + } +} + +int DP[10001] = { 1 }; + +int main() { + ifstream cin("exercise.in"); + ofstream cout("exercise.out"); + + int N, M; + cin >> N >> M; + sieve(N); + for (auto& p : pr) { + for (int i = N; i >= 0; --i) { + for (int j = p; j <= N - i; j *= p) DP[i + j] = ((ll)j * DP[i] + DP[i + j]) % M; + } + } + int ans = 0; + for (int i = 0; i <= N; ++i) ans = (DP[i] + ans) % M; + cout << ans << '\n'; +} |