3994: [SDOI2015]约数个数和

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1379  Solved: 962
[Submit][Status][Discuss]

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
【题解】好神啊…LHC书上写的乱七八糟看不懂啊》。。《
这个方法好…通俗易懂

/********************************************

	Title		BZOJ3994.cpp
	Author 		TomatoLoveCoconut
	Time		2018-3-30
	History		Created 2018-3-30
	
	Version		1.0.0
	
	Tags:		莫比乌斯反演


	while(true) RP++;
	
		 QAQ

*********************************************/


#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define base 311
#define mod 19270817
#define maxlongint 2147483647
#define maxint 32767
#define pi (double)acos(-1.0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
//SGT
#define MID (l+r)>>1
#define lson o<<1
#define rson o<<1|1
//clear the array
#define cla(a) memset(a,0,sizeof(a))
#define clb(a) memset(a,INF,sizeof(a));
#define clc(a) memset(a,-1,sizeof(a));
#define maxn 50010


using namespace std;


//complex
struct Complex{
    double x,y;
    Complex(double xx=0,double yy=0){x=xx,y=yy;}
};
inline Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
inline Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
inline Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.y*b.x+b.y*a.x);}
//BIT
inline int lowbit(int x){return x&(-x);}




//var
ll mu[maxn+5],sum[maxn+5],C_sum[maxn+5];
int isprime[maxn+5],prime[maxn+5],cnt=0;
int Cnt[maxn+5];
inline void pre()
{
	for (int i=1;i<=maxn;i++)
		isprime[i]=1;
	mu[1]=1;
	sum[1]=1;
	for (int i=2;i<=maxn;i++)
	{
		if (isprime[i])
		{
			prime[++cnt]=i;
			mu[i]=-1;
			sum[i]=2;
			Cnt[i]=1;
		}
		for (int j=1;j<=cnt && (i*prime[j])<=maxn;j++)
		{
			int x=i*prime[j];
			isprime[x]=0;
			if (i%prime[j]==0)
			{
				mu[x]=0;
				Cnt[x]=Cnt[i]+1;
				sum[x]=sum[i]/(Cnt[i]+1)*(Cnt[x]+1);
				break;
			}
			else{
				mu[x]=-mu[i];
				sum[x]=sum[i]*2;
				Cnt[x]=1;
			}
		}
	}
	for (int i=1;i<=maxn;i++) mu[i]+=mu[i-1];
	for (int i=1;i<=maxn;i++) C_sum[i]=C_sum[i-1]+sum[i];
}
int n,m;

inline ll F(int n,int m)
{
	if (n>m) swap(n,m);
	ll ans=0;
	for (int i=1,j=1;i<=n;i=j+1)
	{
		j=min(n/(n/i),m/(m/i));
		ans=(ll)ans+(ll)(mu[j]-mu[i-1])*(ll)C_sum[n/i]*(ll)C_sum[m/i];
	}
	return ans;
}


int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	pre();
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&n,&m);
		cout<<F(n,m)<<endl;
	}
	return 0;
}

0 条评论

发表评论

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