洛谷1072 Hankson 的趣味题

一年前做了然而却还是不会系列。

题意

给出 $a_0,a_1,b_0,b_1$ ，需要求 $x$ ，使得

$$\begin{cases} gcd(x,a_0)=a_1 \\ lcm(x,b_0)=b_1 \end{cases}$$

题解

显然，对于

$$gcd(x,y)=k$$

我们可以将其化为

$$gcd(\dfrac{x}{k},\dfrac{y}{k})=1$$

又因为

$$lcm(x,y)=k$$

可以化为

$$gcd(x,y)=\dfrac{x\times y}{k}$$

那么可以用上述性质将题意转化为：

$$\begin{cases} gcd(\dfrac{x}{a_1},\dfrac{a_0}{a_1})=1 \\ gcd(\dfrac{b_1}{x},\dfrac{b_1}{b_0})=1 \end{cases}$$

显然 $\dfrac{x}{a_1},\dfrac{b_1}{x}\in N^{\ast}$ ，所以可以在 $\le \sqrt {b_1}$ 的范围内枚举 $x$ ，这样也可以得到另一个可能符合条件的 $y=b_1\div x$ ，把 $x,y$ 分别带入上式进行验证即可。需要注意 $x\neq y$ 。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,a0,a1,b0,b1;

int gcd(int x,int y) { return y ? gcd(y,x%y) : x; }

int main()
{
    n=read();
    while (n--)
    {
        a0=read(); a1=read(); b0=read(); b1=read();
        int x=a0/a1,y=b1/b0,ans=0;
        int sqn=sqrt(b1);
        for (int i=1;i<=sqn;i++)
        {
            if (b1%i) continue;
            int j=b1/i;
            if (i%a1==0 && gcd(i/a1,x)==1 && gcd(j,y)==1) ans++;
            if (i==j) continue;
            if (j%a1==0 && gcd(j/a1,x)==1 && gcd(i,y)==1) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}