51nod 1479 小Y的数论题

一脸不可做题~~~233333

T<=100000，所以一定要logn出解啦。

但是完全没有头绪*&#……%*&……（）……#￥*#@

题解：

因为2^p+2^p=2^(p+1)

发现这个式子和原式很像诶~~~

所以：2^(kab)+2^(kab)=2^(kab+1)

发现，只要选择合适的k，使得(kab+1)|c即可。

即：kab+1=lc

lc-kab=1

exgcd出解。

因为(a,b,c)=1所以一定有解。

然后快速幂整出来x,y,z，对m取余

但是，当m是2的整次幂的时候，可能出现的问题是，x/y/z为0

因为要选择(0,m)的数，所以0不行。

然后，因为m已经是2的整次幂，而且m>=3

所以，可以特殊考虑。

if a>1 x=m/2,y=1,z=1 （因为m/2的次幂一定mod m 为0）

else if b>1 x=1,y=m/2,z=1

else if c>1（此时a，b都是1啦） x=y=z=m/2 （两边都是0）

else (全是1) x=1,y=1,z=2

所以，综上讨论，不会出现无解的情况的。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,b,c,t;

ll m;

ll l,k;

ll x,y,z;

void exgcd(ll a0,ll b0,ll &x,ll &y){

    if(b0==){

        x=,y=;return;

    }

    exgcd(b0,a0%b0,y,x);

    y-=(a0/b0)*x;

}

ll qm(ll x,ll y){

    ll ret=;

    while(y){

        if(y&) ret=(ret*x)%m;

        x=(x*x)%m;

        y>>=;

    }

    return ret%m;

}

int main(){

    scanf("%lld",&t);

    while(t--){

        scanf("%lld",&m);

        scanf("%lld%lld%lld",&a,&b,&c);

        l=,k=;

        exgcd(c,a*b,l,k);

        k=-k;

        if(k<){

            ll p=(-k)/c+;

            k=k+c*p;

            l=l+p*a*b;

        }

        else if(k>){

            ll p=k/c;

            k-=p*c;

            l-=p*a*b;

        }

        x=qm(,k*b);

        y=qm(,k*a);

        z=qm(,l);

        if(x==||y==||z==){

            if(a>){

                x=m/;

                y=;z=;

            }

            else if(b>){

                y=m/;

                x=;z=;

            }

            else if(c>){

                x=y=z=m/;

            }

            else {

                x=,y=,z=;

            }

        }

        printf("%lld %lld %lld\n",x,y,z);

    }

}

总结：

这种题怎么想？？

瞎搞好了。

怎么就能想到2^(kab)+2^(kab)=2^(kab+1)呢？鬼知道。

(xa+yb) Mod m=(zc) Mod m

巴特西

51nod 1479 小Y的数论题

最新文章

热门文章