SGU140. Integer Sequences

https://codeforces.com/problemsets/acmsguru/problem/99999/140

n元同余方程的求解

对于任意二元我们可以替换成kgcd(a,b)，不断迭代下去最后会变成ax=b(mod p)的情况，然后，再返回去求解，得到g，然后后面变成不等式求解，直接将y[i-1]*g即可，但是要最小整数解。过程当中不断的用p取模，这样可以保证结果不会很大。因为只要一个结果，通项公式为b/d的一个组合，小的约束小，大的约束大， 大的一定包含在小的里面，那么大的一定是其中的一个解，所以mod p，但这并不是最小解，而是一个整数解。

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 ll ex_gcd(ll a,ll b,ll &x,ll &y)
 5 {
 6     if(!b){x=1,y=0;return a;}
 7     ll d=ex_gcd(b,a%b,x,y);
 8     ll tmp=x;
 9     x=y;y=tmp-a/b*y;
10     return d;
11 }
12 const ll N=520;
13 ll n,m[N],p,b,x[N],y[N],ans[N];
14 int main()
15 {
16     scanf("%lld%lld%lld",&n,&p,&b);
17     for(int i=1;i<=n;i++) scanf("%lld",&m[i]),m[i]%=p;
18     ll g=m[1];m[n+1]=p;
19     for(int i=1;i<=n;i++) g=ex_gcd(g,m[i+1],x[i],y[i]);
20     if(b%g) printf("NO\n");
21     else 
22     {
23         printf("YES\n");
24         g=b/g,y[0]=1;
25         for(int i=n;i>=1;i--)
26         {
27             g=(g*x[i]%p+p)%p;
28             ans[i]=(g*y[i-1]%p+p)%p;
29         }
30         for(int i=1;i<=n;i++) printf("%lld%c",ans[i],(i==n?'\n':' '));
31      } 
32     return 0;
33  }