题目描述

Description

神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了，于是向你来请教……多组输入

Input

第一行一个整数T 表述数据组数接下来T行，每行两个正整数，表示N, M

Output

T行，每行一个整数表示第i组数据的结果

Sample Input

2
10 10
100 100

Sample Output

30
2791

HINT

T = 10000
N, M <= 10000000

题目分析

题目要我们求
推导过程如下：






令

令
这个东西是能在枚举求出来的 之后按照套路分块计算即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long miu[10002333],prime[10002333>>1];
bool v[10002333];
long long f[10002333];
void work()
{
    miu[1]=1;
    for(int i=2;i<=10000000;i++)
    {
        if(!v[i]) prime[++prime[0]]=i,miu[i]=-1;
        for(int j=1;j<=prime[0]&&i*prime[j]<=10000000;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]) miu[i*prime[j]]=-miu[i];
            else break;
        }
    }
    for(int i=1;i<=prime[0];i++)
        for(int j=1;j*prime[i]<=10000000;j++) f[j*prime[i]]+=miu[j];
    for(int i=1;i<=10000000;i++) f[i]+=f[i-1];
}
long long calc(long long x,long long y)
{
    if(x>y) swap(x,y);
    long long sum=0,last=0;
    for(long long i=1;i<=x;i=last+1)
    {
        last=min(x/(x/i),y/(y/i));
        sum+=(f[last]-f[i-1])*(x/i)*(y/i);
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    work();
    for(int i=1;i<=t;i++)
    {
        long long x,y;
        scanf("%lld%lld",&x,&y);
        printf("%lld\n",calc(x,y));
    }
    return 0;
}