fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4.  
  5. // ———— change #1: prime modulus 10^9+7 ————
  6. const ll mod = 10000007;
  7.  
  8. // fast i/o / debug timers left untouched
  9. void Code_By_Mohamed_Khaled() {
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     cout.tie(nullptr);
  13. #ifndef ONLINE_JUDGE
  14.     freopen("input.txt", "r", stdin);
  15.     freopen("output.txt", "w", stdout);
  16. #endif
  17. }
  18. void Time() {
  19. #ifndef ONLINE_JUDGE
  20.     cout<<"\n";
  21.     auto end = chrono::high_resolution_clock::now();
  22.     auto duration = chrono::duration_cast<chrono::microseconds>(end - chrono::high_resolution_clock::now());
  23.     cout << "Time taken: " << duration.count() << " microseconds" << endl;
  24. #endif
  25. }
  26.  
  27. // safe modular ops
  28. ll add(ll a, ll b) { return (a + b) % mod; }
  29. ll mul(ll a, ll b) { return (a * b) % mod; }
  30. ll sub(ll a, ll b) { return (a - b + mod) % mod; }
  31.  
  32. // ———— SPF sieve up to 1e6 ————
  33. static const int MAXN = 1000000;
  34. vector<int> spf(MAXN+1, 1);
  35. void precompute_spf() {
  36.     for (int i = 2; i <= MAXN; i++) {
  37.         if (spf[i] == 1) {
  38.             for (ll j = i; j <= MAXN; j += i) {
  39.                 if (spf[j] == 1) spf[j] = i;
  40.             }
  41.         }
  42.     }
  43. }
  44.  
  45. // fast exponentiation (only used for inv‑build below)
  46. ll fast_power(ll base, ll exp) {
  47.     ll res = 1;
  48.     while (exp) {
  49.         if (exp & 1) res = mul(res, base);
  50.         base = mul(base, base);
  51.         exp >>= 1;
  52.     }
  53.     return res;
  54. }
  55.  
  56. // ———— change #2: build inv[] up to mod ————
  57. vector<ll> inv;  // size will be mod+5
  58. void build_inverses() {
  59.     inv.resize(mod+5);
  60.     inv[1] = 1;
  61.     for (int i = 2; i < mod; i++) {
  62.         // only valid because mod is prime
  63.         inv[i] = mul(mod - mod/i, inv[mod % i]);
  64.     }
  65. }
  66.  
  67. // factor n by SPF
  68. void prime_fact(ll n, vector<pair<int,int>>& fac) {
  69.     while (n > 1) {
  70.         int p = spf[n], cnt = 0;
  71.         while (n % p == 0) {
  72.             n /= p;
  73.             cnt++;
  74.         }
  75.         fac.emplace_back(p, cnt);
  76.     }
  77. }
  78.  
  79. // ans[i] = sndd(i!) mod
  80. vector<ll> ans(MAXN+1);
  81.  
  82. int main(){
  83.     Code_By_Mohamed_Khaled();
  84.  
  85.     precompute_spf();
  86.     build_inverses();
  87.  
  88.     // orig[p] = current exponent of prime p in (i-1)!
  89.     vector<int> orig(MAXN+1, 0);
  90.  
  91.     // x = running product of [ (e_p+1)*(e_p+2)/2 ] over all primes p seen so far
  92.     ll x = 1;
  93.  
  94.     auto get_sum = [&](ll e)->ll {
  95.         // (e+1)(e+2)/2  mod
  96.         ll t = mul(e+1, e+2);
  97.         return mul(t, inv[2]);
  98.     };
  99.  
  100.     // precompute ans[1..MAXN]
  101.     for (int i = 1; i <= MAXN; i++) {
  102.         vector<pair<int,int>> fac;
  103.         prime_fact(i, fac);
  104.         for (auto &it : fac) {
  105.             int p = it.first;
  106.             int cnt = it.second;
  107.  
  108.             ll old_e = orig[p];
  109.             ll new_e = old_e + cnt;
  110.  
  111.             ll old_sum = get_sum(old_e);
  112.             ll new_sum = get_sum(new_e);
  113.  
  114.             // divide out the old prime‐term, multiply in the new one
  115.             x = mul(x, new_sum);
  116.             x = mul(x, inv[old_sum]);
  117.  
  118.             orig[p] = new_e;
  119.         }
  120.         ans[i] = x;
  121.     }
  122.  
  123.     // answer queries
  124.     ll n;
  125.     while (cin >> n && n > 0) {
  126.         cout << ans[n] << "\n";
  127.     }
  128.  
  129.     Time();
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 0.61s 96884KB
comments (?)
stdin
copy 
4
5
757494
0
stdout
copy 
30
90
0
https://ideone.com/ehOfqZ
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!