• 周五. 9月 30th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【poj2891】Strange Way to Express Integers

admin

11月 28, 2021

题意:

给出n个模方程x=a(mod r) 求x的最小解

题解:

这就是个线性模方程组的模版题- – 但是有一些要注意的地方

extgcd算出来的解x可能负数  要让x=(x%mo+mo)%mo

而且mo不是等于lcm(r1,r2) 而是r2/gcd(r1,r2)

代码:

 1 #include <cstdio>
 2 typedef long long ll;
 3 ll n,a,r;
 4 ll extgcd(ll &x,ll &y,ll a,ll b){
 5     if (!b){
 6         x=1,y=0;
 7         return a;
 8     }else{
 9         ll res=extgcd(x,y,b,a%b);
10         ll t=x;
11         x=y;
12         y=t-a/b*y;
13         return res;
14     }
15 }
16 int main(){
17     while (scanf("%I64d",&n)!=EOF){
18         scanf("%I64d%I64d",&r,&a);
19         ll x,y,a1,r1;
20         bool bo=1;
21         for (ll i=2;i<=n;i++){
22             scanf("%I64d%I64d",&r1,&a1);
23             ll gc=extgcd(x,y,r,r1);
24             if ((a1-a)%gc) bo=0;
25             ll mo=r1/gc;
26             x=(x*(a1-a)/gc%mo+mo)%mo;
27             a+=r*x;
28             r*=r1/gc;
29         }
30         if (!bo) puts("-1");
31         else printf("%I64d
",a);
32     }
33 }

View Code

发表回复

您的电子邮箱地址不会被公开。