题目大意及输入描述：
给两个整数n和q 表示序列长度和询问个数
然后n个整数 表示序列里的ai
然后q行，每行三个整数op,x,y：
op=1为修改操作，表示将所有下标是x的因数的数加上y；
op=2为询问操作，求[x,y]区间的和。
数据范围：
n,q<=10^5,x<=2*10^9,y<=10^9
思路：
我当时没有认为可行的思路 所以直接用树状数组和√n求因数 的这种暴力做法勉勉强强拿到70分。
其实有一个思路，我没细想(细想大概也会认为不行)，以为不行，但其实是我后来ac的做法：
筛x的素数，然后根据筛出来的素数去组合成x的所有因数。
题解这么说：
注意到2*10^9内反质数的因数个数在10^3级别，远小于√x，考虑根据利用这个性质进行优化。
质数出现的概率大概在O(1/logx)级别，我们预处理出√2*10^9 范围内的所有质数，用其对 x进行质因数分解。复杂度 O(√x/logx + σ0(x))，可以看做和√n同阶。
发现修改操作有约O(n√n)个，而查询只有 O(n) 个，用O(1)修改,O(√n)查询的分块维护即可。由 于树状数组本身常数小，实现优秀也可以通过。时间复杂度 O(n√n)。
反质数见这里：P1463 [POI2002][HAOI2007]反素数
顺便从这道题记下一个了结论：
若正整数m能分解成m=p1^a1+p2^a2+...+pk^ak（p是质数）
则m的因数个数是(a1+1)*(a2+1)*...*(ak+1)
(与接下来无关)
然后我这么做了，用树状数组，一个样例超时，加了快读就卡过去了。
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int maxn=2e5+5; inline int read(int&x) { char c; while(!isdigit(c=getchar()));x=c-'0'; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-'0'; } int pri[maxn+5]={0},isp[maxn+5]={0}; void init() { int p=0; for(int i=2;i<=maxn;i++) { if(!isp[i])pri[++p]=i; for(int j=1;j<=p&&i*pri[j]<=maxn;j++) { isp[i*pri[j]]=1; if(i%pri[j]==0)break; } } } int n; ll c[maxn]; inline void update(int x,ll v) { while(x<=n){c[x]+=v;x+=x&-x;} } inline ll getsum(int x) { ll ans=0; while(x){ans+=c[x];x-=x&-x;} return ans; } inline ll sum(int l,int r) { return getsum(r)-getsum(l-1); } int fac[maxn]; inline void dfs(int v,int fa,int id,int y) { if(id>fac[0])return; dfs(v,fa,id+1,y); v*=fac[id]; while(fa%v==0) { update(v,y); if(fa/v>=fac[id+1])dfs(v,fa,id+1,y); v*=fac[id]; } } int main() { init(); int q,op,x,y,tx; read(n);read(q); for(int i=1;i<=n;i++) { read(x);update(i,x); } while(q--) { read(op);read(x);read(y); if(op==1) { fac[0]=0;tx=x; for(int i=1;pri[i]<=tx;i++) { if(pri[i]>n)break; if(tx%pri[i]==0) { fac[++fac[0]]=pri[i]; while(tx%pri[i]==0)tx/=pri[i]; } } if(fac[0])dfs(1,x,1,y); update(1,y); } else { printf("%lld ",sum(x,y)); } } }