[NOIP2009] $Hankson$ 的趣味题 (数论,gcd)

题目链接

Solution

此题,用到的结论都是比较浅显的,但是,我竟然没想到反过来枚举...

只有50分... 被自己蠢哭...

结论比较浅显:

1.对于两个正整数$a$,$b$,设 $gcd(a,b)=k$,则存在$gcd(a/k,b/k)=1$.

也就是说 $x=k_1*a_1$,$a_0=k_2*a_1$,它们最大公约数为$a_1$,那么要求 $k_1$ 与 $k_2$ 必须互质,否则它们的最大公约数会是 $gcd(k_1,k_2)*a_1$.

2.对于两个正整数$a$,$b$,设$lcm(a,b)=k$,则存在$gcd(k/a,k/b)=1$.

比较浅显,可以由 $a*b=gcd(a,b)*lcm(a,b)$ 推出来.

然后通过分析题意结论,便可以分析出 $x$ 满足 $x$ 是 $b_1$ 的因子,并且满足是 $a_1$ 的倍数.

所以我们直接 $\sqrt{b_1}$ 枚举其因子,并且判断是否满足上述条件即可.

### Code
### 100 分做法
```cpp
#include
#define ll long long
using namespace std;
ll n,a1,a0,b0,b1;

ll gcd(ll x,ll y)

{

if(y==0)return x;

else return gcd(y,x%y);

}

int main()

{

scanf("%lld",&n);

while(n--)

{

scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);

if(b1%a1!=0){printf("0\n");continue;}

ll ans=0,maxx=sqrt(b1);

for(int x=1;x<=maxx;x++)

{

if(b1%x!=0)continue;

if(x%a10)

if(gcd(b1/b0,b1/x)1)

if(gcd(x/a1,a0/a1)1)

ans++;

if(b1/xx)continue;

ll y=b1/x;

if(y%a10)

if(gcd(b1/b0,b1/y)1)

if(gcd(y/a1,a0/a1)==1)

ans++;

}

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

}

}

### 50 分做法(暴力枚举 $a_1$ 的倍数,然后判断)

```cpp

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n,a1,a0,b0,b1;

ll gcd(ll x,ll y)

{

    if(y==0)return x;

    else return gcd(y,x%y);

}

int main()

{

    scanf("%lld",&n);

    while(n--)

    {

        scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);

        if(b1%a1!=0){printf("0\n");continue;}

        ll tt=0,ans=0;

        while(1)

        {

            tt++;

            if(tt*a1>b1)break;

            ll x=tt*a1;

            if(b1%x!=0)continue;

            if(gcd(x,a0)!=a1)continue;

            if(x*b0!=gcd(b0,x)*b1)continue;

            ans++;

        }

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

    }

}

巴特西

[NOIP2009] $Hankson$ 的趣味题 (数论,gcd)

题目链接

Solution

最新文章

热门文章