SGU140. Integer Sequences

2021/8/1 6:06:08

本文主要是介绍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<bits/stdc++.h>
 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  } 

 



这篇关于SGU140. Integer Sequences的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程