题目描述
(由于本题是数论题，所以我只把题目大意说一下。。。)
输入时给定\(a_0,a_1,b_0,b_1\)，题目要求你求出满足如下条件的\(x\)的个数:
\[\begin{cases}\gcd(a_0,x)=a_1 \cdots\cdots 1 \\
\operatorname{lcm}(b_0,x)=b_1 \cdots\cdots2\end{cases}\]
基本思路
先上一波推导:
我们很容易可以得到：
\[\gcd(a \times d,b \times d)=d \times \gcd(a,b)
\]
所以根据这个规律以及\(\gcd\)的定义，由\(1\)式可知:
\[\gcd(a_0/a_1,x/a_1)=1 \cdots\cdots 3
\]
根据\(\operatorname{lcm}\)的定义:
\[\operatorname{lcm}(a,b)=a \times b/\gcd(a,b)
\]
即
\[\gcd(a,b)=a \times b/\operatorname{lcm}(a,b)
\]
所以由\(2\)式可得:
\[\gcd(b_0,x)=b_0 \times x/b_1
\]
进行类似于对\(1\)式的变换:
\[\gcd(b_1/x,b_1/b_0)=1 \cdots\cdots4
\]
联立\(3\)式和\(4\)式:
\[\begin{cases}\gcd(a_0/a_1,x/a_1)=1\\
\gcd(b_1/x,b_1/b_0)=1\end{cases} \cdots\cdots5\]
还可以观察到:
\[\begin{cases}a_1|x\\x|b_1\end{cases} \cdots\cdots6
\]
所以我们便得到了一种方法：\(O(\sqrt{N})\)扫一遍\(b_1\)的约数判断是否满足\(5\)式和\(6\)式，统计答案
细节注意事项
在扫描\(b_1\)的约数时，会得到两个约数：\(x\)和\(b_1/x\)特别注意当\(x=b_1/x\)即\(x^2=b_1\)时合法的\(x\)只计算一次。
参考代码
#include<cstdio>
#define rg register
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
template <typename T> inline T read(){
T s=0;bool f=false;char c=getchar();
while(c<'0'||c>'9')f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
return (f)?(-s):(s);
}
int main(){
int T=read<int>();
while(T--){
int a0=read<int>(),a1=read<int>();
int b0=read<int>(),b1=read<int>();
int tmp1=a0/a1,tmp2=b1/b0,ans=0;
for(rg int x=1;x*x<=b1;x++)
if(b1%x==0){
int y=b1/x;
if(x%a1==0&&gcd(x/a1,tmp1)==1&&gcd(tmp2,b1/x)==1) ans++;
if(x==y) continue;
if(y%a1==0&&gcd(y/a1,tmp1)==1&&gcd(tmp2,b1/y)==1) ans++;
}
printf("%d\n",ans);
}
return 0;
}
完结撒花\(qwq\)