【题解】Hankson 的趣味题 数学 洛谷 P1072 -DyRisingSunlight

注：本题解为转载题解，内容大意为洛谷题解中的头篇题解，但该文章内容全部为本人自己总结所写，题解原网址，之所以要写本篇题解是为了加深理解。

Problem’s Website

洛谷 P1072

Problem’s Main Idea

• $n$个询问，每个询问给定 $a_0, a_1, b_0, b_1$, 求有多少个 $x$满足 $\gcd(a_0,x)=a_1,\ \mathrm{lcm}(b_0,x)=b_1$。
• 数据范围：$n \le 2e3,1 \le a_0,a_1,b_0,b_1 \le 2e9$

Solution

找规律推结论。
$\gcd(a_0,x)=a_1$

$\Rightarrow \ \begin{cases} x=k_1 \times a_1 \\ a_0=k_2 \times a_1 \ \end{cases}$

$\Rightarrow \ \gcd(k_1,k_2)=1$
证明（反证法）

设 $\gcd(k_1,k_2) = K (K \not= 1)$
$\Rightarrow \ \begin{cases} k_1=p \times K\\ k_2=q \times K \end{cases}$

$\Rightarrow \ \begin{cases} x=p \times K \times a_1\\ a_0=q \times K \times a_1 \end{cases}$

$\Rightarrow \ \gcd(x,a_0)=K \times a_1 \not= a_1$

与条件不符。
故 $\gcd(x / a_1,a_0/a_1)=1$

我们再把结论推广一下：
$\forall a,b \in N_{+},\ \gcd(a,b)=k$
$\Rightarrow \ \gcd(a/k,b/k)=1$

我们再来看关于 $\mathrm{lcm}$的一些结论
$\mathrm{lcm}(b_0, x)=b_1$
$\Rightarrow \ b_0 \times x / \gcd(b_0,x) = b_1$
$\therefore \gcd(b_0,x)=b_0 \times x / \mathrm{lcm}(b_0,x)=b_0 \times x / b_1$
$\Rightarrow \ \gcd(b_0/(b_0 \times x / b_1),x/(b_0 \times x / b_1)) = 1$
$\Rightarrow \ \gcd(b_1/x,b_1/b_0) = 1$

整理上述内容，我们可以得到下列式子
$\begin{cases} \gcd(x/a_1,a_0/a_1)=1 \\ \gcd(b_1/x,b_1/b_0)=1 \end{cases}$

也就是说，$x$是 $a_1$的倍数且是 $b_1$的因数

所以我们就可以直接枚举了，试除法枚举 $b_1$的因数，然后按照上述式子判断一下，如果符合，则答案++。

Code

//Coded by Dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
typedef long long ll;
#define int ll
int sc()
{
    int xx = 0, ff = 1; char cch = gc;
    while(!isdigit(cch) && cch != EOF)
    {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(isdigit(cch))
    {
        xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
void out(int x)
{
    if(x < 0) pc('-'), x = -x;
    if(x >= 10) out(x / 10);
    pc(x % 10 + '0');
}
#undef int
ll n, a0, a1, b0, b1, ans;
ll gcd(ll x, ll y)
{
    if(y == 0) return x;
    return gcd(y, x % y);
}
int main()
{
    n = sc();
    while(n--)
    {
        ans = 0;
        a0 = sc(), a1 = sc(), b0 = sc(), b1 = sc();
        for(ll i = 1; i * i <= b1; ++i)
        {
            if(b1 % i == 0)
            {
                if(i % a1 == 0 && gcd(b1 / b0, b1 / i) == 1 && gcd(i / a1, a0 / a1) == 1) ++ans;
                if(b1 / i != i)
                {
                    ll tem = b1 / i;
                    if(tem % a1 == 0 && gcd(b1 / b0, b1 / tem) == 1 && gcd(tem / a1, a0 / a1) == 1) ++ans;
                }
            }
        }
        out(ans), pc('\n');
    }
    return 0;
}

$$
2019 \ CSP-S \ Rp++
$$