【BZOJ 2820】YY 的 GCD / 题解

BZOJ原题地址

洛谷原题地址

题目描述

给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对。

输入输出

输入格式

第一行一个整数T 表述数据组数。

接下来T行，每行两个正整数，表示N, M。

输出格式

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

样例

输入

2
10 10
100 100

输出

30
2791

思路

我们要求的是 $sum_{i=1}^{n}sum_{j=1}^{m}[gcd(x,y)=prime]$。
然后。。。

坑。

代码

#include 
#define maxn 10001000
#define ll long long
using namespace std;
bool vis[maxn];
ll s[maxn];
int pri[maxn],top;
int mu[maxn],g[maxn];
void Init(int n){
    mu[1]=1;
    for (int i=2;i<=n;++i){
        if (!vis[i]) mu[i]=-1,pri[++top]=i;
        for (int j=1;j<=top&&pri[j]*i<=n;++j){
            vis[i*pri[j]]=1;
            if (i%pri[j]==0) break;
            mu[pri[j]*i]=-mu[i];
        }
    }
    for (int j=1;j<=top;j++)
        for (int i=1;i*pri[j]<=n;i++)
            g[i*pri[j]]+=mu[i];
    for (int i=1;i<=n;i++)
        s[i]=s[i-1]+(ll)g[i];
}
int main(){
    ios::sync_with_stdio(false);
    Init(maxn-1);
    int T;cin>>T;while(T--){
        int n,m;
        cin>>n>>m;
        if (n>m) swap(n,m);
        ll ans=0;
        for (int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            ans+=(ll)(n/l)*(m/l)*(s[r]-s[l-1]);
        }
        cout<