BZOJ3994[SDOI2015] 约数个数和

 1 //It is made by ljh2000
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #include <set>
13 #include <string>
14 using namespace std;
15 typedef long long LL;
16 const int MAXN = 50011;
17 int n,m,mobius[MAXN],prime[MAXN],cnt,g[MAXN],nex;
18 bool vis[MAXN];
19 LL ans;
20 //ans=∑mobius[i]*g[n/d]*g[m/d];
21 //g[i]=∑[n/i];
22 inline int getint(){
23     int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
24     if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
25 }
26 
27 inline void init(){
28     mobius[1]=1; 
29     for(int i=2;i<=50000;i++) {
30         if(!vis[i]) { prime[++cnt]=i; mobius[i]=-1; }
31         for(int j=1;j<=cnt && prime[j]*i<=50000;j++) {
32             vis[i*prime[j]]=1;
33             if(i%prime[j]==0) { mobius[i*prime[j]]=0; break; }
34             mobius[i*prime[j]]=-mobius[i];
35         }
36     }
37     for(int i=2;i<=50000;i++) mobius[i]+=mobius[i-1];
38     for(int o=1;o<=50000;o++) {
39         for(int i=1;i<=o;i=nex+1){
40             nex=min(o,o/(o/i));
41             g[o]+=(nex-i+1)*(o/i);
42         }
43     }
44 }
45 
46 inline void calc(){
47     for(int d=1;d<=n;d=nex+1) {
48         nex=min(n/(n/d),m/(m/d));
49         ans+=(LL)(mobius[nex]-mobius[d-1])*g[n/d]*g[m/d];/*!!!*/
50     }
51 }
52 
53 inline void work(){
54     int T=getint(); init();
55     while(T--) {
56         n=getint(); m=getint(); if(n>m) swap(n,m);
57         ans=0; calc();
58         printf("%lld\n",ans);
59     }
60 }
61 
62 int main()
63 {
64     work();
65     return 0;
66 }