fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb emplace_back
  6. #define fo(i, n) for(int i = 1; i <= n; ++i)
  7.  
  8. typedef long long ll;
  9.  
  10. const int N = 1000300;
  11. const int mod = 1e9 + 7;
  12.  
  13. int lp[N];
  14. int l[200200], r[200200];
  15. int a[200200], n, q;
  16. int ans[200200];
  17. int cnt[N];
  18. int X[N];
  19. vector<int> e[200200];
  20.  
  21. inline void sieve() {
  22.     for(int i = 2; i <= 1000000; ++i) {
  23.         if(!lp[i]) {
  24.             lp[i] = i;
  25.             if(i * 1ll * i <= 1000000)
  26.                 for(int j = i * i; j <= 1000000; j += i)
  27.                     lp[j] = i;
  28.         }
  29.     }
  30. }
  31. vector<pair<int, int> > primes;
  32. vector<int> divi, pr;
  33.  
  34. inline void calc(int p = 0, int x = 1) {
  35.     if(p == primes.size()) {
  36.         divi.pb(x);
  37.         return;
  38.     }
  39.     calc(p + 1, x);
  40.     for(int i = 0; i < primes[p].second; ++i) {
  41.         x *= primes[p].first;
  42.         calc(p + 1, x);
  43.     }
  44. }
  45.  
  46. inline void gen_divisors(int n)
  47. {
  48.     primes.clear();
  49.     divi.clear();
  50.     while(n > 1)
  51.     {
  52.         int x = lp[n], st = 0;
  53.         while(n % x == 0) n /= x, st++;
  54.         primes.pb(x, st);
  55.     }
  56.     calc();
  57. }
  58.  
  59. int sign, cur_id, s2;
  60.  
  61. inline void gen_masks(int p = 0, int x = 1, int c = 0) {
  62.     if(p == pr.size()) {
  63.         if(c) s2 = -1;
  64.         else s2 = 1;
  65.         ans[cur_id] += cnt[x] * s2 * sign;
  66.         return ;
  67.     }
  68.     gen_masks(p + 1, x * pr[p], c ^ 1);
  69.     gen_masks(p + 1, x, c);
  70. }
  71.  
  72. int main() {
  73.     ios::sync_with_stdio(0); cin.tie(0);
  74.     sieve();
  75.     cin >> n;
  76.     fo(i, n) {
  77.         cin >> a[i];
  78.     }
  79.     cin >> q;
  80.     fo(it, q) {
  81.         cin >> l[it] >> r[it] >> X[it];
  82.         e[l[it]-1].pb(-it);
  83.         e[r[it]].pb(it);
  84.     }
  85.     fo(i, n) {
  86.         gen_divisors(a[i]);
  87.         for(int j : divi) cnt[j]++;
  88.         for(int t = 0; t < e[i].size(); ++t) {
  89.             int id = e[i][t], x = X[abs(id)];
  90.             pr.clear();
  91.             while(x > 1) {
  92.                 int y = lp[x];
  93.                 pr.pb(y);
  94.                 while(x % y == 0) x /= y;
  95.             }
  96.             sign = (id < 0 ? -1 : 1), cur_id = abs(id);
  97.             gen_masks();
  98.         }
  99.     }
  100.     fo(it, q) cout << ans[it] << '\n';
  101.  
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 11468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RW7RFT
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!