一脸不可做题~~~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