思路
题目要求
$sumlimits_{i=1}^nsumlimits_{j=1}^m [(i,j)为素数]$
枚举一个素数，考虑它的贡献
$sumlimits_psumlimits_{i=1}^{n}sumlimits_{j=1}^{m} [(i,j)=p]$
后面的利用bzoj 1101的做法。
$sumlimits_psumlimits_{i=1}^{lfloorfrac{n}{p} floor}sumlimits_{j=1}^{lfloorfrac{m}{p} floor} [(i,j)=1]$
$sumlimits_p sumlimits_{d=1}^{min(lfloorfrac{n}{p}
floor,lfloorfrac{m}{p}
floor)}μ(d)lfloorfrac{n}{pd}
floorlfloorfrac{m}{pd}
floor$
设T=pd，枚举T，再枚举T的素因数p，那么d也就等于T/p
$sumlimits_Tsumlimits_{p|T}μ(frac{T}{p})lfloorfrac{n}{T} floorlfloorfrac{m}{T} floor$
后面那一块只跟前面的T有关，所以可以提前。
$sumlimits_Tlfloorfrac{n}{T} floorlfloorfrac{m}{T} floor（sumlimits_{p|T}μ(frac{T}{p})）$
将后面的预处理出来。
参考popoqqq的课件，之间枚举一个素数，然后更新p*1,p*2...。
复杂度：1/1+1/2+1/3+...+1/n=O(logn)
代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 6 using namespace std; 7 8 const int N = 10000000; 9 typedef long long LL; 10 11 bool noprime[N+5]; 12 int pri[N+5],tot,mu[N+5],g[N+5]; 13 14 inline int read() { 15 int x = 0,f = 1;char ch = getchar(); 16 for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1; 17 for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0'; 18 return x * f; 19 } 20 void init() { 21 mu[1] = 1; //- 22 for (int i=2; i<=N; ++i) { 23 if (!noprime[i]) pri[++tot] = i,mu[i] = -1; 24 for (int j=1; j<=tot&&i*pri[j]<=N; ++j) { 25 noprime[i*pri[j]] = true; 26 if (i % pri[j] == 0) {mu[i*pri[j]] = 0;break;} 27 mu[i*pri[j]] = -mu[i]; 28 } 29 } 30 for (int j=1; j<=tot; ++j) 31 for (int i=pri[j]; i<=N; i+=pri[j]) 32 g[i] += mu[i/pri[j]]; 33 for (int i=1; i<=N; ++i) g[i] += g[i-1]; 34 } 35 void work(int n,int m) { 36 LL ans = 0; 37 int c = min(n,m),p; 38 for (int i=1; i<=c; i=p+1) { 39 p = min(n/(n/i),m/(m/i)); 40 ans += 1ll*(g[p]-g[i-1])*(n/i)*(m/i); 41 } 42 printf("%lld ",ans); 43 } 44 int main() { 45 init(); 46 int Case = read(); 47 while (Case--) { 48 int n = read(),m = read(); 49 work(n,m); 50 } 51 return 0; 52 }