fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define PI acos(-1)
  4. #define mp make_pair
  5. #define F first
  6. #define sd(x) scanf("%d",&x)
  7. #define sd2(x,y) scanf("%d%d",&x,&y)
  8. #define sdl(x) scanf("%lld",&x)
  9. #define sd2l(x,y) scanf("%lld%lld",&x,&y)
  10. #define S second
  11. #define ll long long int
  12. #define inf 1000000014
  13. #define infl (ll)(1e18+250)
  14. #define sz(x) (int) x.size()
  15. #define pi pair< int , int >
  16. #define pil pair <pi, pi>
  17. #define pii pair<int, pair>
  18. #define nax 201010
  19. #define pu push
  20. #define trace1(x)  cerr << #x << ": " << x << endl
  21. #define trace2(x, y)  cerr << #x << ": " << x << " | " << #y << ": " << y << endl
  22. using namespace std;
  23. #define ll long long int
  24. #define MOD 100000007
  25. #define MAX 5000550
  26. int cnt[MAX];
  27. pi v[MAX][13];
  28. vector < pi > query;
  29. vector < int > primes;
  30. int occ[MAX];
  31. int latest[MAX];
  32. ll times[MAX];
  33. int prime_mapping[MAX];
  34. long long int fans[110];
  35. ll cnt_primes[MAX];
  36. int query_cnt;
  37. void pre()
  38. {
  39. 	// prime factorization
  40.     int ctr,cpy;
  41.     for(int i = 2; i <= 5000100; i++)
  42.     {
  43.         if(cnt[i] == 0)
  44.         {
  45.             primes.push_back(i); // indexing the primes.
  46.             prime_mapping[i] = sz(primes) - 1; // prime to index mapping
  47.             for(int j = i ; j <= 5000100; j+=i)
  48.             {
  49.                 cpy = j;
  50.                 ctr = 0;
  51.                 while(cpy % i == 0)
  52.                 {
  53.                     cpy /= i;
  54.                     ctr++;
  55.                 }
  56.                 v[j][cnt[j]++] = make_pair(i,ctr); // stores the pair <prime_factor, its count> for element j
  57.             }
  58.         }
  59.     }
  60. }
  61. void solve()
  62. {
  63. 	// We try to answer all queries in one pass through all the elements , for this we order the queries in ascending order and answer
  64.     ll cur_ans;int siz, num, count;
  65.     int query_ptr = 0;
  66.     // trivial case n = 1; note after sorting the queries n = 1 will occur at the start so we first deal with them
  67.     while(query_ptr <= query_cnt && query[query_ptr].first == 1)
  68.     {
  69.           fans[query[query_ptr].second]  = 1;
  70.           query_ptr++;
  71.     } 
  72.     /*
  73.     	We update two arrays on the fly , occ and cnt_primes
  74.     	at any iteration i occ[x] (x = prime) holds the number of times x occurs in factorization of factorial (i)
  75.     	Similarly for iteration i cnt_primes[x] holds the number of times x occurs in prime factorization of AF(i)
  76. 		latest[x] (x = prime) holds the last value till which we have calculated the number of times x occurs in prime factorization of i
  77. 		The trick is that although prime_factor x occurs in all factorials > x, we update the occ , latest and cnt_primes arrays only
  78. 		when i % x == 0. We can do so because between any two successive multiples of x say A and B all numbers in [A, B) will have same number of 
  79. 		x in prime factorization of their factorial. This is clear because no multiple of x occurs in (A,B) so once you calculate the requiste values for
  80. 		A for all factorials A+1, A+2, A+x-1 the number of x's remain constant (occ[x]). Notice this in line 90. 
  81.     */
  82.     for(int i = 2; i <= 5000000; i++)
  83.     {
  84.         siz = cnt[i];
  85.         for(int j = 0; j < siz ; j++)
  86.         {
  87.             num = v[i][j].first;
  88.             count = v[i][j].second;
  89.             if(latest[num] != 0)
  90.                 cnt_primes[prime_mapping[num]] = (cnt_primes[prime_mapping[num]] + occ[num]*1ll*(i - latest[num] - 1) ) % MOD;
  91.             occ[num] += count;
  92.             cnt_primes[prime_mapping[num]] += occ[num];
  93.             latest[num] = i;
  94.         }
  95.         /* Explanation of answering query.
  96.            Suppose we want to find the answer for element i. Notice that for any prime number(x) < i we would have the correct answer till just smaller
  97.            multiple of x i.e till [i / x](integer division) * i (denoted by Y)using the above methodology. Now we would have to add the number of times x occurs in the range
  98. 		   [Y + 1 , i]. We again use the same argument we used to justify first loop, which is that the number of times x occurs in factorials in range (Y+1, I] would be constant
  99. 		   Hence the similar term in line 109. Accordingly we also modify lates[x] denoting that we have the number of times prime factor x occurs in AF[i] , till
  100. 		   number i
  101. 		*/
  102.         if(query_ptr <= query_cnt && query[query_ptr].first == i)
  103.         {
  104.             int psiz = sz(primes);
  105.             int prime_ptr =  0;
  106.             ll cans = 1;
  107.             while(primes[prime_ptr] <= i)
  108.             {
  109.                 cnt_primes[prime_ptr] = (cnt_primes[prime_ptr] + occ[primes[prime_ptr]]*1ll*(i - latest[primes[prime_ptr]]) ) % MOD;
  110.                 cans = cans * (cnt_primes[prime_ptr] + 1) % MOD;
  111.                 latest[primes[prime_ptr]] = i;
  112.                 prime_ptr++;
  113.             }
  114.             while(query_ptr <= query_cnt && query[query_ptr].first == i)
  115.             {
  116.                 fans[query[query_ptr].second] = cans;
  117.                 query_ptr++;
  118.             }
  119.         }
  120.         if(query_ptr > query_cnt)
  121.             break;
  122.     }
  123.     for(int i = 0; i < query_cnt; i++)
  124.         printf("%lld\n", fans[i]);
  125. }
  126. int main()
  127. {
  128. 	//freopen("input.txt","r",stdin);
  129.     //freopen("output.txt","w",stdout);
  130.     int n;
  131.     pre();
  132.     while(cin >> n)
  133.     {
  134.         if(n == 0)
  135.             break;
  136.         query.push_back(make_pair(n , query_cnt));
  137.         query_cnt++;
  138.     }
  139.     sort(query.begin(), query.end()); // ordering the queries in ascending order
  140.     solve();
  141.     return 0;
  142. }
  143.  
Success #stdin #stdout 0.96s 593048KB
comments (?)
stdin
copy 
1
2
3
4
100
0
stdout
copy 
1
2
6
18
59417661
https://ideone.com/m04Uif
language:
C++14 (gcc 8.3)
created:
5 years 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!