批:赛时没想到 $(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;
}