【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;" (i%pri[j]="=0)" break; mu[pri[j]*i]="-mu[i];" } i="1;i*pri[j]<=n;i++)" g[i*pri[j]]+="mu[i];" s[i]="s[i-1]+(ll)g[i];" int main(){ ios::sync_with_stdio(false); init(maxn-1); 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<