%%%Po姐姐
https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html
【题意】
见原题
【题解】
一个数对(x,y)的公约数必定是其最大公约数的约数。所以我们可以设F（d）为d的所有约数之和，之后只要用F(d)代替最大公约数为d的数对的公约数之和就行了。
先不考虑a的限制，原题就转化为：
$\sum_{i= 1}^{n}\sum_{j= 1}^{m}F\left ( Gcd(i,j) \right )$
=$\sum_{d= 1}^{n} F(d)\cdot g(d)$ //g(d)代表gcd为d的对数。
=$\sum_{d= 1}^{n} F(d) \sum_{d|i}^{}\left \lfloor n/i \right \rfloor\left \lfloor m/i \right \rfloor \cdot μ(i/d)$
=$\sum_{i= 1}^{min(n,m)}\left \lfloor n/i \right \rfloor\left \lfloor m/i \right \rfloor \sum_{d|i}^{} μ(i/d)*F(d)$
然后按照套路，对i求一下片段和。
当然还有a的限制。仔细想如果F(d)>a,实际上就把F(d)当成0就行了。可是每次询问都要重新求修改F(d)岂不是会T掉？
于是你可以离线操作，按a值将询问排个序，每次只要将小于等于a的F(d)在之前的询问基础上修改一下就行了。
对于F(n)和μ(n)线性筛求一遍。还有模数问题直接int自然溢出就行了，最后负数再处理一下就行了。
时间复杂度应该就是O（$T\sqrt{n}logn$+$n log^{2} n$）
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define N 100005 5 using namespace std; 6 struct Q 7 { 8 int n,m,a,id; 9 }a[20005]; 10 struct node 11 { 12 int x,y; 13 }f[N]; 14 int l,n,m,po,last,cnt,T,F[N],ans[20005],prime[N],tot[N],sum[N],tre[N],mu[N]; 15 bool flag[N]; 16 bool cmp(Q a,Q b) 17 { 18 return a.a<b.a; 19 } 20 bool cmp2(node a,node b) 21 { 22 return a.x<b.x; 23 } 24 void Pre() 25 { 26 int x;F[1]=1;mu[1]=1; 27 for (int i=2;i<N;++i) 28 { 29 if (!flag[i]) 30 { 31 prime[++cnt]=i; 32 F[i]=1; 33 tot[i]=i; 34 sum[i]=1+i; 35 mu[i]=-1; 36 } 37 for (int j=1;j<=cnt;++j) 38 { 39 x=i*prime[j]; 40 if (x>=N) break; 41 flag[x]=1; 42 if (i%prime[j]) 43 { 44 F[x]=F[i]*sum[i]; 45 tot[x]=prime[j]; 46 sum[x]=1+prime[j]; 47 mu[x]=-mu[i]; 48 } 49 else 50 { 51 F[x]=F[i]; 52 tot[x]=tot[i]*prime[j]; 53 sum[x]=sum[i]+tot[x]; 54 break; 55 } 56 } 57 F[i]*=sum[i]; 58 } 59 for (int i=1;i<N;++i) f[i]={F[i],i}; 60 } 61 void add(int x,int y) 62 { 63 for (;x<N;x+=x&(-x)) tre[x]+=y; 64 } 65 int get(int x) 66 { 67 int s=0; 68 for (;x;x-=x&(-x)) s+=tre[x]; 69 return s; 70 } 71 void join(int x,int d) 72 { 73 for (int i=d;i<N;i+=d) add(i,x*mu[i/d]); 74 } 75 int main() 76 { 77 Pre(); 78 scanf("%d",&T); 79 for (int i=1;i<=T;++i) 80 { 81 scanf("%d%d%d",&a[i].n,&a[i].m,&a[i].a); 82 a[i].id=i; 83 } 84 sort(a+1,a+T+1,cmp); 85 sort(f+1,f+N,cmp2); 86 po=1; 87 for (int i=1;i<=T;++i) 88 { 89 while (po<N && f[po].x<=a[i].a) 90 { 91 join(f[po].x,f[po].y),++po; 92 } 93 last=0; n=a[i].n; m=a[i].m; 94 l=min(n,m); 95 for (int j=1;j<=l;j=last+1) 96 { 97 last=min(min(n/(n/j),m/(m/j)),l); 98 ans[a[i].id]+=(n/j)*(m/j)*(get(last)-get(j-1)); 99 } 100 } 101 for (int i=1;i<=T;++i) 102 printf("%d\n",ans[i]<0?ans[i]+2147483648:ans[i]); 103 return 0; 104 }