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==0){
        x=1,y=0;return;
    }
    exgcd(b0,a0%b0,y,x);
    y-=(a0/b0)*x;
}
ll qm(ll x,ll y){
    ll ret=1;
    while(y){
        if(y&1) ret=(ret*x)%m;
        x=(x*x)%m;
        y>>=1;
    }
    return ret%m;
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&m);
        scanf("%lld%lld%lld",&a,&b,&c);
        l=0,k=0;
        exgcd(c,a*b,l,k);
        k=-k;
        if(k<0){
            ll p=(-k)/c+1;
            k=k+c*p;
            l=l+p*a*b;
        }
        else if(k>0){
            ll p=k/c;
            k-=p*c;
            l-=p*a*b;
        }
        x=qm(2,k*b);
        y=qm(2,k*a);
        z=qm(2,l);
        if(x==0||y==0||z==0){
            if(a>1){
                x=m/2;
                y=1;z=1;
            }
            else if(b>1){
                y=m/2;
                x=1;z=1;
            }
            else if(c>1){
                x=y=z=m/2;
            }
            else {
                x=1,y=1,z=2;
            }
        }
        printf("%lld %lld %lld
",x,y,z);
    }
}

总结：

这种题怎么想？？

瞎搞好了。

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