两个长度为N序列A和X,有sum(Ai*Xi)≡B (mod M),先给出序列A,整数B,M,求一组可行的序列X,无解输出NO。
首先如果N为1,a*x≡B (mod M),这个式子等价与 a*x+M*y=B,显然这个式子是可以用扩展gcd求出来的。
若N为2 既,a*x+by≡B(mod M),等价于a*x+b*y+M*=B,此时首先求式子a*x+b*y=gcd(a,b),记x1=x,x2=y,原式变为kx+Mz=B,在求一次扩展GCD记y1=x,x3=z,此时N=2的解也求出来了,既X={x1*y1,x2*y1,x3}。
同理,N>2时,每次求解前两个子式并合并,最终得到两个序列x和y,然后处理处最终答案即可。
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <queue> using namespace std; typedef long long ll; ll gcd(ll a,ll b,ll &xx,ll &yy) { if (b==0) { xx=1; yy=0; return a; } ll d=gcd(b,a%b,xx,yy); ll t=xx; xx=yy; yy=t-a/b*yy; return d; } ll gcd(ll a,ll b) { if (b==0) return a; return gcd(b,a%b); } ll x[230],y[230]; ll a[230]; ll n,m,b,k,p; int main() { // freopen("in.txt","r",stdin); cin>>n>>m>>b; for (int i=1; i<=n; i++) { cin>>a[i]; a[i]%=m; } k=gcd(a[1],a[2],x[1],x[2]); for (int i=3; i<=n; i++) { k=gcd(k,a[i],y[i-2],x[i]); } ll ck=gcd(k,m,y[n-1],x[n+1]); if (b % ck!=0) { cout<<"NO"<<endl; return 0; } else { cout<<"YES"<<endl; ll mul=1; for (int i=n+1; i>=1; i--) { while (x[i]<0) x[i]+=m; x[i]=x[i]*mul%m; if (i>2) { while (y[i-2]<0) y[i-2]+=m; mul=mul*y[i-2]%m; } } for (int i=1; i<=n; i++) cout<<(x[i]*b/k)%m<<" "; cout<<endl; } return 0; }