CF1967D2 补题笔记

ShanQing · 2024-05-02 12:57:00 · 题解

批：赛时没想到 (p+q) \mid d 所以推复杂了还整出了奇怪的欧拉函数，喜提罚坐，快说我菜/kk。

首先经典套路，设 d=\gcd(a,b)，然后 a=pd，b=qd，显然有 \gcd(p,q)=1，原式变为 (pd+qd) \mid (qd^2) 。

两边同除 d，原式变为 (p+q) \mid (qd) 。

由 \gcd(p,q)=1 得 \gcd(p+q,q)=1，所以只能有 (p+q) \mid d 。

由于 d=\frac{a}{p}，又因为显然 p<d，所以有 p<\frac{a}{p}<\frac{n}{p}，即 p^2<n。同理，q^2<m。

于是就成功地缩小了 p 和 q 的范围。这时候就可以枚举所有满足 \gcd(p,q)=1 的数对，对于每一对数对 d 的取值范围显然为 \min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{q}\right\rfloor)，然后又要满足 (p+q) \mid d ，所以贡献即为 \frac{\min(\left\lfloor\frac{n}{p}\right\rfloor,\left\lfloor\frac{m}{q}\right\rfloor)}{p+q}。

code

//writer:Oier_szc

#include <bits/stdc++.h>
//#include <windows.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N=2e3+5,INF=2e9,mod=1e9+7;
int t,n,m;
int bad[N][N];
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
signed main() {
    scanf("%lld",&t);
    while(t--) {
        scanf("%lld%lld",&n,&m);
        int ans=0;
        for(int a=1;a<=n/a;++a) {
            for(int b=1;b<=m/b;++b) {
                if(gcd(a,b)==1) ans+=min(n/a,m/b)/(a+b);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}