Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<vector>
- #include <string>
- #include<algorithm>
- #include <iostream>
- #include <queue>
- #include<set>
- #include<unordered_set>
- #include<stack>
- #include<cmath>
- #include<math.h>
- #include<map>
- #include<unordered_map>
- #include<unordered_map>
- #include<random>
- #include<chrono>
- #include<ctime>
- #ifdef PERVEEVM_LOCAL
- std::mt19937 rnd(238);
- #else
- std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- #endif
- // #include<ext/rope>
- using namespace std;
- typedef long long ll;
- typedef pair<long long, long long> pll;
- #define mp make_pair
- #define fi(b, c) for(ll i = b; i <= c; i++)
- #define fj(b, c) for(ll j = b; j <= c; j++)
- #define fk(b, c) for(ll k = b; k <= c; k++)
- #define fq(b, c) for(ll q = b; q <= c; q++)
- #define fw(b, c) for(ll w = b; w <= c; w++)
- #define fim(b, c) for(ll i = b; i >= c; i--)
- #define fjm(b, c) for(ll j = b; j >= c; j--)
- #define fkm(b, c) for(l k = b; k >= c; k--)
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- // #define sz(a) (ll)(a.size())
- #define fs first
- #define sd second
- #define endl "\n"
- #define sz(x) (ll)(x.size())
- template <class T>
- inline istream& operator >> (istream& in, vector <T>& a) {
- for (auto& i : a)
- in >> i;
- return in;
- }
- template <class T>
- inline ostream& operator << (ostream& out, vector <T>& a) {
- for (auto& i : a)
- out << i << "\n";
- return out;
- }
- template <class T, class U>
- inline istream& operator >> (istream& in, vector <pair <T, U>>& a) {
- for (auto& i : a)
- in >> i.first >> i.second;
- return in;
- }
- template <class T, class U>
- inline ostream& operator << (ostream& out, vector <pair <T, U>>& a) {
- for (auto& i : a)
- out << i.first << "" << i.second << endl;
- return out;
- }
- const ll inf = 1e9 + 123, llinf = 1e18 + 829, ura = 684395049517;
- void xru(){
- // setlocale(LC_ALL, "rus");
- // freopen(".in", "r", stdin);
- // freopen(".out", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- void run(){
- cout<<endl;
- system("pause");
- }
- ///////////////////////////////////////////////
- const ll MAXN = 10000;
- const ll PRCNT = 1229;
- ll n;
- vector<vector<ll>> t(PRCNT, vector<ll>(MAXN));
- vector<ll> a(MAXN);
- ///////////////////////////////////////////////
- ll sum(ll r, ll dv){
- ll result = 0;
- for(; r >= 0; r = (r & (r+1)) - 1){
- result += t[dv][r];
- }
- return result;
- }
- ll sum(ll l, ll r, ll dv){
- if(l == 0) return sum(r, dv);
- return sum(r, dv) - sum(l-1, dv);
- }
- void upd(ll id, ll x, ll dv){
- for(; id < n; id = (id | (id+1))) t[dv][id] += x;
- }
- void build(ll dv){
- fi(0, n-1) upd(i, a[i], dv);
- }
- void add(ll id, ll x, vector<ll> &siege){
- while(x != 1){
- ll cnt = 1;
- while(siege[x] == siege[x/siege[x]]){
- cnt++;
- x /= siege[x];
- }
- // cout << siege[x] << "-" << cnt << endl;
- upd(id, cnt, siege[x]);
- x /= siege[x];
- }
- }
- void sub(ll id, ll x, vector<ll> &siege){
- while(x != 1){
- ll cnt = 1;
- while(siege[x] == siege[x/siege[x]]){
- cnt++;
- x /= siege[x];
- }
- upd(id, -cnt, siege[x]);
- x /= siege[x];
- }
- }
- int main() {
- xru();
- vector<bool> prime(MAXN + 1, true);
- vector<ll> pr(PRCNT), num(MAXN), siege(MAXN, inf);
- prime[0] = prime[1] = false;
- ll ct = 0;
- fi(2, MAXN){
- if(prime[i]){
- pr[ct] = i;
- ct++;
- siege[i] = i;
- if(i*i <= MAXN){
- for(ll j = i*i; j<=MAXN; j+=i){
- prime[j] = 0;
- siege[j] = min(i, siege[j]);
- }
- }
- }
- }
- fi(0, PRCNT-1) {
- num[pr[i]] = i;
- }
- cin >> n;
- fi(0, n-1){
- cin >> a[i];
- }
- // fi(2, MAXN) <<i<<"-"<< siege[i] << " ";
- // add(0, 5, siege);
- fi(0, n-1){
- add(i, a[i], siege);
- }
- ll q;
- cin >> q;
- // cout << sum(0, n-1, 5);
- while(q--){
- ll typ;
- cin >> typ;
- if(typ == 0){
- ll id, x;
- cin >> id >> x;
- id--;
- sub(id, a[id], siege);
- a[id] = x;
- add(id, a[id], siege);
- } else {
- ll l, r;
- cin >> l >> r;
- l--, r--;
- ll ans = 1;
- fi(0, PRCNT-1){
- // if(sum(l, r, i) > 0) cout << i << "-" << sum(l, r, i) << endl;
- ans = ans * (sum(l, r, i) + 1) % (ll)(1e9+7);
- }
- cout << ans << endl;
- }
- }
- // run();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement