【NOIP2009】Hankson的趣味题

题意：给出 $a_0$, $a_1$, $b_0$, $b_1$, 求出正整数 $x$ 的个数，$x$ 满足：

$gcd(x,a_0)=a_1$ , $lcm(x, b_0)=b_1$ 。

题解：预备知识：设 $a= {p_1}^{a_1}{p_2}^{{a_2}}{p_3}^{{a_3}}...{p_n}^{{a_n}}$，$b= {p_1}^{b_1}{p_2}^{{b_2}}{p_3}^{{a_3}}...{p_n}^{{b_n}}$ ，则有：

$gcd(a,b)={p_1}^{min(a_1,b_1)}{p_2}^{min(a_2,b_2)}{p_3}^{min(a_3,b_3)}...{p_n}^{min(a_n,b_n)}$

$lcm(a,b)={p_1}^{max(a_1,b_1)}{p_2}^{max(a_2,b_2)}{p_3}^{max(a_3,b_3)}...{p_n}^{max(a_n,b_n)}$

根据题目结合上面的性质可以得到如下做法：

考虑枚举质因数 ${p_x}$ ，设 $a_0$ 的质因数中 $p_x$ 的系数为 $t_1$ ，$a_1$ 的系数为 $t_2$ , $x$ 的系数为 $t$ ，由前面性质可得：$min(t, t_1)=t_2$ 。分情况讨论：如果 $t_1 < t_2$ ，那么无解；如果 $t_1=t_2$ , 那么 $t$ 要满足 $t \geq t_2$ ；如果 $t_1 \gt t_2$ ，那么 $t = t_2$ .

同理，设 $b_0$ 的质因数中 $p_x$ 的系数为 $t_3$ ，$a_1$ 的系数为 $t_4$ , $x$ 的系数为 $t$ ，由前面性质可得：$max(t, t_3)=t_4$ 。分情况讨论：如果 $t_3 \gt t_4$ ，那么无解；如果 $t_3=t_4$ , 那么 $t$ 要满足 $t \leq t_4$ ；如果 $t_3 \lt t_4$ ，那么 $t = t_4$ .

把上面两个合并分类讨论可得：当 $t_2=t_1$ 且 $t_4=t_3$ 且 $t_4 \ge t_2$ ，此时 $t_2 \le t \le t_4$ , $ans$ *= $t_4-t_2+1$ .

下面是无解的 $3$ 种情况（可简化）：

$t_2=t_1$ 且 $t_4=t_3$ 且 $t_4 \lt t_2$，无解
$t_2 \lt t_1$ 或 $t_4 \gt t_3$ ，无解
$t_2 \gt t_1$ 且 $t_4 \lt t_3$ 且 $ t_2 ≠ t_4$，无解

其他情况对 $ans$ 无影响 ( $ans$ *= $1$ ).

枚举质因数范围为 $\sqrt{b_1}$ （仅枚举 $b_1$ 的质因数），故总时间复杂度约为 $ O(n\sqrt{b_1})$ ，可以通过。

#include<cstdio>

inline int _read()

{

    int x=0; char c;

    for(;c<'0'||c>'9';c=getchar());

    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+c-'0';

    return x;

}

const int N=100000;

bool b[N];

int prime[N],tot,a0,a1,b0,b1,ans;

void GetPrime()

{

    for(int i=2;i<=50000;i++)

        if(!b[i])

        {

            prime[++tot]=i;

            for(long long j=1ll*i*i;j<=50000;j+=i) b[j]=true;

        }

}

void work(int p)

{

    int t1=0,t2=0,t3=0,t4=0;

    for(;a0%p==0;a0/=p)t1++;//求次数

    for(;a1%p==0;a1/=p)t2++;

    for(;b0%p==0;b0/=p)t3++;

    for(;b1%p==0;b1/=p)t4++;

    if(t1==t2&&t3==t4)

    {

        if(t1<=t3) ans*=(t3-t1+1);

        else ans=0; //ans=0即无解

    }

    if(t1<t2||t3>t4) ans=0;

    if(t1>t2&&t3<t4&&t2!=t4) ans=0;

}

int main()

{

    int T=_read();

    GetPrime(); //预处理质数

    while(T--)

    {

        ans=1;

        a0=_read(),a1=_read(),b0=_read(),b1=_read();

        for(int i=1;i<=tot;i++)

            if(b1%prime[i]==0) work(prime[i]);

            //枚举b1的质因数

        if(b1>1) work(b1);

        printf("%d\n",ans);

    }

}

巴特西

【NOIP2009】Hankson的趣味题

最新文章

热门文章