Advertisement
Ginger_samurai

Untitled

Sep 4th, 2020
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.63 KB | None | 0 0
  1. #include<vector>
  2. #include <string>
  3. #include<algorithm>
  4. #include <iostream>
  5. #include <queue>
  6. #include<set>
  7. #include<unordered_set>
  8. #include<stack>
  9. #include<cmath>
  10. #include<math.h>
  11. #include<map>
  12. #include<unordered_map>
  13. #include<unordered_map>
  14. #include<random>
  15. #include<chrono>
  16. #include<ctime>
  17. #ifdef PERVEEVM_LOCAL
  18.     std::mt19937 rnd(238);
  19. #else
  20.     std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  21. #endif
  22. // #include<ext/rope>
  23. using namespace std;
  24. typedef long long ll;
  25. typedef pair<long long, long long> pll;
  26. #define mp make_pair
  27. #define fi(b, c) for(ll i = b; i <= c; i++)
  28. #define fj(b, c) for(ll j = b; j <= c; j++)
  29. #define fk(b, c) for(ll k = b; k <= c; k++)
  30. #define fq(b, c) for(ll q = b; q <= c; q++)
  31. #define fw(b, c) for(ll w = b; w <= c; w++)
  32. #define fim(b, c) for(ll i = b; i >= c; i--)
  33. #define fjm(b, c) for(ll j = b; j >= c; j--)
  34. #define fkm(b, c) for(l k = b; k >= c; k--)
  35. #define all(a) a.begin(), a.end()
  36. #define rall(a) a.rbegin(), a.rend()
  37. // #define sz(a) (ll)(a.size())
  38. #define fs first
  39. #define sd second
  40. #define endl "\n"
  41. #define sz(x) (ll)(x.size())
  42. template <class T>
  43. inline istream& operator >> (istream& in, vector <T>& a) {
  44.     for (auto& i : a)
  45.         in >> i;
  46.     return in;
  47. }
  48. template <class T>
  49. inline ostream& operator << (ostream& out, vector <T>& a) {
  50.     for (auto& i : a)
  51.         out << i << "\n";
  52.     return out;
  53. }
  54. template <class T, class U>
  55. inline istream& operator >> (istream& in, vector <pair <T, U>>& a) {
  56.     for (auto& i : a)
  57.         in >> i.first >> i.second;
  58.     return in;
  59. }
  60. template <class T, class U>
  61. inline ostream& operator << (ostream& out, vector <pair <T, U>>& a) {
  62.     for (auto& i : a)
  63.         out << i.first << "" << i.second << endl;
  64.     return out;
  65. }
  66. const ll inf = 1e9 + 123, llinf = 1e18 + 829, ura = 684395049517;
  67. void xru(){
  68. //  setlocale(LC_ALL, "rus");
  69. //  freopen(".in", "r", stdin);
  70. //  freopen(".out", "w", stdout);
  71.  ios_base::sync_with_stdio(false);
  72.  cin.tie(NULL);
  73.  cout.tie(NULL);
  74. }
  75. void run(){
  76.     cout<<endl;
  77.     system("pause");
  78. }
  79.  
  80. ///////////////////////////////////////////////
  81. const ll MAXN = 10000;
  82. const ll PRCNT = 1229;
  83. ll n;
  84. vector<vector<ll>> t(PRCNT, vector<ll>(MAXN));
  85. vector<ll> a(MAXN);
  86. ///////////////////////////////////////////////
  87.  
  88. ll sum(ll r, ll dv){
  89.     ll result = 0;
  90.     for(; r >= 0; r = (r & (r+1)) - 1){
  91.         result += t[dv][r];
  92.     }
  93.     return result;
  94. }
  95. ll sum(ll l, ll r, ll dv){
  96.     if(l == 0) return sum(r, dv);
  97.     return sum(r, dv) - sum(l-1, dv);
  98. }
  99. void upd(ll id, ll x, ll dv){
  100.     for(; id < n; id = (id | (id+1))) t[dv][id] += x;
  101. }
  102. void build(ll dv){
  103.     fi(0, n-1) upd(i, a[i], dv);
  104. }
  105.  
  106. void add(ll id, ll x, vector<ll> &siege){
  107.     while(x != 1){
  108.         ll cnt = 1;
  109.         while(siege[x] == siege[x/siege[x]]){
  110.             cnt++;
  111.             x /= siege[x];
  112.         }
  113.         // cout << siege[x] << "-" << cnt << endl;
  114.         upd(id, cnt, siege[x]);
  115.         x /= siege[x];
  116.     }
  117. }
  118. void sub(ll id, ll x, vector<ll> &siege){
  119.     while(x != 1){
  120.         ll cnt = 1;
  121.         while(siege[x] == siege[x/siege[x]]){
  122.             cnt++;
  123.             x /= siege[x];
  124.         }
  125.         upd(id, -cnt, siege[x]);
  126.         x /= siege[x];
  127.     }
  128. }
  129.  
  130. int main() {
  131.     xru();
  132.     vector<bool> prime(MAXN + 1, true);
  133.     vector<ll> pr(PRCNT), num(MAXN), siege(MAXN, inf);
  134.     prime[0] = prime[1] = false;
  135.     ll ct = 0;
  136.     fi(2, MAXN){
  137.         if(prime[i]){
  138.             pr[ct] = i;
  139.             ct++;
  140.             siege[i] = i;
  141.             if(i*i <= MAXN){
  142.                 for(ll j = i*i; j<=MAXN; j+=i){
  143.                     prime[j] = 0;
  144.                     siege[j] = min(i, siege[j]);
  145.                 }
  146.             }
  147.         }
  148.     }
  149.     fi(0, PRCNT-1) {
  150.         num[pr[i]] = i;
  151.     }
  152.  
  153.     cin >> n;
  154.     fi(0, n-1){
  155.         cin >> a[i];
  156.     }
  157.     // fi(2, MAXN)  <<i<<"-"<< siege[i] << " ";
  158.     // add(0, 5, siege);
  159.     fi(0, n-1){
  160.         add(i, a[i], siege);
  161.     }
  162.  
  163.     ll q;
  164.     cin >> q;
  165.     // cout << sum(0, n-1, 5);
  166.     while(q--){
  167.         ll typ;
  168.         cin >> typ;
  169.         if(typ == 0){
  170.             ll id, x;
  171.             cin >> id >> x;
  172.             id--;
  173.             sub(id, a[id], siege);
  174.             a[id] = x;
  175.             add(id, a[id], siege);
  176.         } else {
  177.             ll l, r;
  178.             cin >> l >> r;
  179.             l--, r--;
  180.             ll ans = 1;
  181.             fi(0, PRCNT-1){
  182.                 // if(sum(l, r, i) > 0) cout << i << "-" << sum(l, r, i) << endl;
  183.                 ans = ans * (sum(l, r, i) + 1) % (ll)(1e9+7);
  184.             }
  185.             cout << ans << endl;
  186.         }
  187.     }
  188.     // run();
  189. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement