洛谷P1072 [NOIP2009 提高组] Hankson 的趣味题

@Pelom  October 12, 2021

题意:

求不定方程组

$$ \left\{ \begin{aligned} & (x,a_0) & = & & a_1 \\ & [x,b_0] & = & & b_1 \end{aligned} \right. $$

的正整数解的个数。

数据范围: $1 \le a_0,a_1,b_0,b_1 \le 2000000000$

题解:

由 $gcd$ 及 $lcm$ 的性质得:

$$ \left\{ \begin{aligned} & (\frac{x}{a_1},\frac{a_0}{a_1}) & = & & 1 \\ & (\frac{b_1}{x},\frac{b_1}{b_0}) & = & & 1 \end{aligned} \right. $$

可得 $a_1 \mid x$ 且 $x \mid b_1$,于是可 $\sqrt{b_1}$ 枚举 $b_1$ 因数,验证其满足上式。

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int t,a0,a1,b0,b1;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    scanf("%d",&t);
    for(;t--;){
        scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
        int p=a0/a1,q=b1/b0,ans=0;
        for(int i=1,j;i*i<=b1;i++){
            if(b1%i!=0)
                continue;
            j=b1/i;
            if(i%a1==0 && gcd(i/a1,p)==1 && gcd(b1/i,q)==1)
                ans++;
            if(i==j)
                continue;
            if(j%a1==0 && gcd(j/a1,p)==1 && gcd(b1/j,q)==1)
                ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

优化:

上述算法过于暴力,而其复杂度不够优秀,所以考虑优化。
考虑 $(\frac{b_1}{x},\frac{b_1}{b_0})=1$ ,将 $b_1$ 与 $\frac{b_1}{b_0}$ 的所有相同素因子除去 ,设剩余的数为 $p$ ,则有 $\frac{b_1}{x} \mid p$ 。
继续考虑 $(\frac{x}{a_1},\frac{a_0}{a_1})=1$,同上,将 $p$ 与 $\frac{a_0}{a_1}$ 所有相同素因子除去,得到 $q$ ,此时 $\sqrt{q}$ 枚举 $q$ 的因子,答案即为 $q$ 的因子的个数。
时间复杂度为 $O(\sqrt{q} + \log{q})$ 。


添加新评论