[BZOJ3994] [SDOI2015]约数个数和

题目描述

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

题目分析

前置技能 d(n,m)=injm[gcd(i,j)=1] d(n,m)=\sum\limits _{i|n}\sum\limits_{j|m}[gcd(i,j)=1]
i=1nj=1md(i,j)\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m d(i,j)
=i=1nj=1mxiyj[gcd(x,y)=1] =\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits _{x|i}\sum\limits_{y|j}[gcd(x,y)=1]
=i=1nj=1mxiyjkgcd(i,j)μ(k) =\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits _{x|i}\sum\limits_{y|j}\sum\limits _{k|gcd(i,j)}\mu(k)
=k=1nμ(k)i=1ndj=1mdxiyj1 =\sum\limits_{k=1}^{n}\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} \sum\limits_{x|i} \sum\limits_{y|j}1
=k=1nμ(k)x=1nknkxy=1mkmdy =\sum\limits_{k=1}^{n}\mu(k)\sum\limits_{x=1}^{\lfloor \frac{n}{k} \rfloor}\lfloor \frac{n}{kx} \rfloor\sum\limits_{y=1}^{\lfloor \frac{m}{k} \rfloor}\lfloor \frac{m}{dy} \rfloor

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int t,n,m;
long long miu[100000],prime[100000];
bool vis[100000];
long long f[100000];
void init()
{
    miu[1]=1;
    for(int i=2;i<=50000;i++)
    {
        if(!vis[i]) miu[i]=-1,prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=50000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
            else  miu[i*prime[j]]=-miu[i];
        }
    }
    for(int i=1;i<=50000;i++) miu[i]+=miu[i-1];
    int last=0;
    for(int i=1;i<=50000;i++) 
        for(int j=1;j<=i;j=last+1)
            last=i/(i/j),f[i]+=(last-j+1)*(i/j);

}
long long sum;
int main()
{   
    scanf("%d",&t);
    init();
    while(t--)
    {
        scanf("%d%d",&n,&m);
        int last=0;
        sum=0;
        for(int i=1;i<=n&&i<=m;i=last+1)
        {       
            last=min(n/(n/i),m/(m/i));
            sum+=(miu[last]-miu[i-1])*f[n/i]*f[m/i];
        }
        printf("%lld\n",sum);
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注