BZOJ3994[SDOI2015] 约数个数和

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

    

 

Description

 设d(x)为x的约数个数,给定N、M,求  
 

 

Input

输入文件包含多组测试数据。

第一行,一个整数T,表示测试数据的组数。
接下来的T行,每行两个整数N、M。
 

Output

 T行,每行一个整数,表示你所求的答案。

 

Sample Input

2
7 4
5 6

Sample Output

110
121

HINT

 

 1<=N, M<=50000


1<=T<=50000
 
 
正解:莫比乌斯反演
解题报告:
  莫比乌斯反演推导题。
  推导过程已经写到笔记本上去了…懒得用Tex再写一遍了...
  莫比乌斯反演的题目套路都是得出式子之后,换变量,或者换一个对象计算贡献,根据莫比乌斯函数的性质,想办法做出一个gcd=1的情况。然后再枚举gcd,从而计算整个式子的值。都是套路…
 
 
 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
",ans);
59     }
60 }
61 
62 int main()
63 {
64     work();
65     return 0;
66 }
原文地址:https://www.cnblogs.com/ljh2000-jump/p/6345045.html