杜教筛要预处理+记忆化才拥有正确的复杂度点击查看代码#include<bits/stdc++.h>usingnamespacestd;unordered_map<int,longlong>q1,q2;intv[10000005],prime[1000005],m;intx1[10000005],x2[10000005],S1[10000005];longlongS2[10000005];longlongn,a;long

原题链接题解令\(g=gcd(i,j)\)则\(i=t_1i,j=t_2j\)所以原题等价于求\(\sum_{i\inprime}\sumgcd(x,y)==1,x\in[1,n/i],y\in[1,n/i]\)也就是对于每个素数\(i\)，求\([1,n/i]\)内有几个数互质，我们可以求欧拉函数前缀和得出code#include<bits/stdc++.h>#definelllong