题目描述

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

题目分析

前置技能

#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;
}