Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Mar 31st, 2020 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. using namespace std;
  5.  
  6. void redirect(string filename) {
  7.     freopen((filename + ".out").c_str(), "w", stdout);
  8.     freopen((filename + ".in").c_str(), "r", stdin);
  9. }
  10.  
  11. typedef long long ll;
  12. const ll N = 1e4, PL = 2000;
  13. bool is_comp[N + 1];
  14. vector<ll> primes;
  15. bool is_cached[N + 1][PL + 1];
  16. ll cache[N + 1][PL + 1];
  17. ll n;
  18. ll mod;
  19.  
  20. ll f(ll cn, ll fp) {
  21.     if (cn < 0) {
  22.         return 0;
  23.     }
  24.     if (cn == 0) {
  25.         return 1;
  26.     }
  27.     if (fp >= primes.size()) {
  28.         return 1;
  29.     }
  30.     if (is_cached[cn][fp]) {
  31.         return cache[cn][fp];
  32.     }
  33.     ll res = f(cn, fp + 1);
  34.     for (ll exp = primes[fp]; cn - exp >= 0; exp = exp*primes[fp]) { //had modulus taken on exp updating step (mistake)
  35.         res += (exp*f(cn - exp, fp + 1)) % mod;
  36.         res %= mod;
  37.     }
  38.     cache[cn][fp] = res;
  39.     is_cached[cn][fp] = true;
  40.     return res;
  41. }
  42.  
  43. int main() {
  44.     redirect("exercise");
  45.     ios::sync_with_stdio(false); cin.tie(0);
  46.     cin >> n >> mod;
  47.     for (ll d = 2; d*d <= n; ++d) {
  48.         if (!is_comp[d]) {
  49.             for (ll m = 2*d; m <= n; m += d) {
  50.                 is_comp[m] = true;
  51.             }
  52.         }
  53.     }
  54.     for (ll i = 2; i <= n; ++i) {
  55.         if (!is_comp[i]) {
  56.             primes.emplace_back(i);
  57.         }
  58.     }
  59.     cout << f(n, 0);
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top