From 1ed1261e189fcb1532aea13bf654a62101bde4c9 Mon Sep 17 00:00:00 2001 From: Ta180m Date: Sat, 2 May 2020 23:03:43 -0500 Subject: Create exercise.cpp --- 2020/US Open/Gold/exercise.cpp | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) create mode 100644 2020/US Open/Gold/exercise.cpp 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 +using namespace std; +typedef long long ll; + +int sieve_size; +bitset<10000001> bs; +vector 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'; +} -- cgit v1.2.3-70-g09d2