During several decades, scientists from planet Nibiru are working to create an engine that would allow spacecrafts to fall into hyperspace and move there with superluminal velocity. To check whether their understanding of properties of hyperspace is right, scientists have developed the following experiment. A chain of n particles is placed in hyperspace. Positions of particles in the chain are numbered from 1 to n. Initially, ith particle has charge a i. According to the current theory, if particle number i got special radiation with power d, oscillations would spread by hyperspace and increase by d charge of particles with numbers i, 2 i, 3 i and so on (i.e. with numbers divisible by i). Using a special device, scientists can direct the radiation of the same power at a segment of adjacent particles. For example, suppose that initially there were 6 particles with zero charges, and scientists have sent radiation with power five to particles with numbers 2 and 3. Then charge of 2nd, 3rd, and 4th particles will increase to five, and charge of 6th particle will increase to ten (the oscillations will reach it twice). Charge of other particles won’t change. Charge of particles can’t change without impact of the device. During the experiment, the scientists plan to perform actions of the following types: Measure current charge of the particle number i. Direct radiation with power d at particles with numbers from l to r inclusive. Your program will be given a list of performed actions. For every action of the first type the program should output value of expected charge of the particle calculated in accordance with the current theory described above. If the expected charges of the particles coincide with charges measured during the experiment, it will turn out that scientists’ understanding of hyperspace is right, and they will be able to start building of the hyperdrives. Then inhabitants of Nibiru will finally meet their brothers from Earth in just a few years! Input The first line contains a single integer n — number of particles (1 ≤ n ≤ 3 · 10 5). The second line contains n integers a i separated by spaces — initial charges of the particles (0 ≤ a i ≤ 10 6). The third line contains a single integer q — number of actions in the experiment (1 ≤ q ≤ 3 · 10 5). Each of the following q lines contain two or four integers — a description of the next action in one of the following formats: 1 i — measure current charge of the particle number i (1 ≤ i ≤ n). 2 l r d — direct radiation with power d at particles with numbers from l to r inclusive (1 ≤ l ≤ r ≤ n, 0 ≤ d ≤ 106). Output For each query output the expected charge of the ith particle. Example input output 3 1 2 3 2 2 1 3 5 1 2 12 6 1 2 1 4 5 6 5 2 2 4 2 1 3 1 4 2 3 5 1 1 5 3 8 6
题意：区间修改->【L,R】每个元素的倍数都+val。询问：某个点的值一看就是要用线段树or树状数组的题。但是k倍这一点就比较麻烦。想到可以逆过来，我要求哪些点的时候看因子有没有被处理过就行了。因为避免原来各自的值的影响，我们就设初始所有的数都为0，要问的时候再加a[i]。这样，那对于一个点，它在被修改后的值val，就是其倍数要增加的值。 这样，对于修改，我们仍用树状数组的区间修改。 对于询问，我们就找他的因子和他的单点询问值即可。
AC代码：
#include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include <queue> #include<sstream> #include <stack> #include <set> #include <bitset> #include<vector> #define FAST ios::sync_with_stdio(false) #define abs(a) ((a)>=0?(a):-(a)) #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define mem(a,b) memset(a,b,sizeof(a)) #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,n,a) for(int i=n;i>=a;--i) #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; typedef long long ll; typedef pair<ll,ll> PII; const int maxn = 3e5+200; const int inf=0x3f3f3f3f; const double eps = 1e-7; const double pi=acos(-1.0); const int mod = 1e9+7; inline int lowbit(int x){return x&(-x);} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d); inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;} inline ll inv(ll x,ll p){return qpow(x,p-2,p);} inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;} inline int read(){ int f = 1; int x = 0;char ch = getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; } int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} }; int Map[maxn]; ll sum1[maxn]; ll n,m; void add(int pos, int y) { for(int i=pos;i<=n;i+=lowbit(i)) sum1[i] += y; } void add_range(int l, int r,int x) { add(l,x), add(r+1,-x); } ll ask(int p) { ll ans = 0; for(int i = p; i>=1; i -= lowbit(i)) ans += sum1[i]; return ans; } int main() { n = read(); rep(i,1,n) { Map[i] = read(); } m = read(); rep(i,1,m) { int flag; flag = read(); if(flag==2) { int l,r,dd; l = read(), r = read(), dd = read(); add_range(l,r,dd); } else { int pos; pos = read(); ll ans = Map[pos]; int up = sqrt(pos*1.0); rep(i,1,up) { if(pos%i==0) { ans += ask(i); if(pos/i!=i) ans += ask(pos/i) ; } } cout<<ans<<'\n'; } } return 0; }