1479 小Y的数论题

基准时间限制：1.5 秒 空间限制：131072 KB 分值: 640 

收藏

关注

小Y喜欢研究数论，并且喜欢提一些奇怪的问题。
这天他找了三个两两互质的数a, b, c，以及另一个数m, 现在他希望找到三个(0, m)范围内的整数x, y, z，使得
 (xa+yb) Mod m=(zc) Mod m 

Input

第一行一个数代表数据组数T
接下来T行每行四个整数m, a, b, c
满足a, b, c两两互质
1 <= T <= 100000
1 <= a, b, c <= 10^9
3 <= m <= 10^9

Output

对于每组数据，如果不存在x, y, z满足条件，则输出"Stupid xiaoy"（不含引号）
否则输出一行三个数分别为x, y, z

Input示例

1
100 1 1 1

Output示例

1 2 3

往扩展欧几里得想

考虑这样的式子
2^kab+2^kab=2^(kab+1)
设x=2^kb,y=2^ka
当c|kab+1时必有合法的z
设c*l=kab+1，则cl-kab=1。
注意a,b,c两两互质，所以gcd(c,ab)=1
用扩展欧几里得即可算出l。
z=2^l
若m是2的幂数，余数为0怎么办？
更好办了。。。
当a>1时x=m/2,y=z=1
否则当b>1时 类似
再否则当c>1时 x=y=z=m/2
若a=b=c=1，x=y=1,z=2
注意
l,k算出来后可能比0小，该怎么做大家都明白吧

需要注意一种情况

如果m是2的幂数，那么就可以特判一下直接输出答案。
当a>1时x=m/2,y=z=1
否则当b>1时，类似
再否则当c>1时，x=y=z=m/2
若a=b=c=1，x=y=1,z=2

 

#include<bits/stdc++.h>
using namespace std;
long long  gcd(long long x,long long y)
{
    return y==0?x:gcd(y,x%y);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        long long r=exgcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
long long qs(long long y,long long p){
    if (y==0) return 1;
    if (y==1) return 2;
    long long s=qs(y/2,p),s1=qs(y%2,p);
    return s*s%p*s1%p;
}
bool flag(long long  x){
    while (x%2==0) x=x/2;
    if (x==1) return 1;return 0;
}

int main()
{
   long long t;
    long long a,b,c,m;
    long long g;
    long long l,k;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld",&m,&a,&b,&c);
        if(!flag(m))
        {


        g=exgcd(c,a*b,l,k);
        k=-k;
        while(l<0||k<0)
        {
            l=l+a*b;
            k=k+c;
        }
        printf("%lld %lld %lld\n",qs(b*k,m),qs(a*k,m),qs(l,m));
        }
        else
        {


         if(a>1){
                printf("%lld 1 1\n",m/2);
            }
            else if(b>1){
                printf("1 %lld 1\n",m/2);
            }
            else if(c>1){
                printf("%lld %lld %lld\n",m/2,m/2,m/2);
            }
            else if(a==b==c){
                printf("1 1 2\n");}

    }
}

}