题目描述

Description

对于任意的>1的n gcd(a, b)不是n^2的倍数
也就是说gcd(a, b)没有一个因子的次数>=2

Input

一个正整数T表示数据组数
接下来T行 每行两个正整数 表示N、M

Output

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

Sample Input

4
2 4
3 3
6 5
8 3

Sample Output

24
28
233
178

HINT

T <= 10000
N, M<=4000000

题目分析

根据莫比乌斯函数的定义 得到:题目要求出



令

快筛出即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,t;
long long mod=1ll<<30;
int prime[4000100];
bool vis[4000100];
long long f[4000100],sum[4000100];
void init()
{
    f[1]=1,sum[1]=1;
    for(int i=2;i<=4000000;i++)
    {
        if(!vis[i]) 
            prime[++prime[0]]=i,f[i]=1-i;
        sum[i]=(sum[i-1]+i)%mod;
        for(int j=1;j<=prime[0]&&i*prime[j]<=4000000;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]) f[i*prime[j]]=(f[i]*f[prime[j]])%mod;
            else if(i%(prime[j]*prime[j])!=0) f[i*prime[j]]=(f[i/prime[j]]*(-prime[j])+mod)%mod; 
        }
    }
    for(int i=1;i<=4000000;i++) f[i]=(((long long)f[i]*i)%mod+f[i-1]+mod)%mod;
}
void work(int x,int y)
{
    int last=0;
    if(x>y) swap(x,y);
    long long ans=0;
    for(int i=1;i<=x;i=last+1)
    {
        last=min(x/(x/i),y/(y/i));
        ans=(ans+((f[last]-f[i-1]+mod)%mod)*(sum[x/i]*sum[y/i])%mod)%mod;
    }
    printf("%lld\n",ans);
}
int main()
{   
    init();
    scanf("%d",&t);
    while(t--)
        scanf("%d%d",&n,&m),work(n,m);
    return 0;
}