Bzoj3994 [SDOI2015]约数个数和-白红宇

Bzoj3994 [SDOI2015]约数个数和

阅读量：6567 次

发布时间：2019-06-24

本文共 1336 字，大约阅读时间需要 4 分钟。

Time Limit: 20 Sec Memory Limit: 128 MB

Submit: 857 Solved: 586

Description

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

Input

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

第一行，一个整数T，表示测试数据的组数。

接下来的T行，每行两个整数N、M。

Output

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

Sample Input

7 4

5 6

Sample Output

110

121

HINT

1<=N, M<=50000

1<=T<=50000

Source

数学问题莫比乌斯反演脑洞题

这里讲得很好http://www.cnblogs.com/mmlz/p/4442452.html

1 /*by SilverN*/ 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #define LL long long 9 using namespace std;10 const int mxn=50010;11 int read(){12 int x=0,f=1;char ch=getchar();13 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}14 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}15 return x*f;16 }17 int pri[mxn],cnt=0;18 int mu[mxn],d[mxn],f[mxn];19 //mu:莫比乌斯函数 d[x]:x的最小质因子的次数 f[x]:x的约数个数 20 int smm[mxn];21 bool vis[mxn];22 void init(){23 mu[1]=1;f[1]=1;24 for(int i=2;i
           
            m)swap(n,m);52 LL res=0;int pos;53 for(int i=1;i<=n;i=pos+1){54 int x=n/i,y=m/i;55 pos=min(n/x,m/y);56 res+=(LL)(smm[pos]-smm[i-1])*(LL)f[x]*f[y];57 }58 return res;59 }60 int n,m;61 int main(){62 int i,j;63 init();64 int T=read();65 while(T--){66 n=read();m=read();67 printf("%lld\n",calc(n,m));68 }69 return 0;70 }