当前位置：网站首页>POJ 2891 Strange Way to Express Integers (Extended Euclidean)

POJ 2891 Strange Way to Express Integers (Extended Euclidean)

2022-08-10 11:09:00 【51CTO】

Description

Elina is reading a book written by Rujia Liu, which introduces a strange way to express non-negative integers. The way is described as following:
Choose k different positive integers a1, a2, …, ak. For some non-negative m, divide it by every ai (1 ≤ i ≤ k) to find the remainder ri. If a1, a2, …, ak are properly chosen, m can be determined, then the pairs (ai, ri) can be used to express m.
“It is easy to calculate the pairs from m, ” said Elina. “But how can I find m from the pairs?”
Since Elina is new to programming, this problem is too difficult for her. Can you help her?

Input

The input contains multiple test cases. Each test cases consists of some lines.
Line 1: Contains the integer k.
Lines 2 ~ k + 1: Each contains a pair of integers ai, ri (1 ≤ i ≤ k).

Output

Output the non-negative integer m on a separate line for each test case. If there are multiple possible values, output the smallest one. If there are no possible values, output -1.

Sample Input

Sample Output

题意

给出一组 mi,ri ,Find the smallest positive integer X ,使得 X%mi=ri ,如果不存在这样的 X 则输出 −1

思路

Because the divisors are not mutually primed,Therefore, the template of the Chinese remainder theorem cannot be directly applied！

Here we use merge 不定方程 的方法,That is, combine the first two equations first,The combined result is then combined with the third equation,Calculated after the final merge X

我们假设 mi 是除数, ri

X%m0=r0 与 X%m1=r1 ,等价于 X=m0×k0+ro=m1×k1+r1 ,其中 ki

联立可得 m0×k0+m1×k1=r1−r0 （因为 ki

Extended Euclidean Algorithm：Integer pairs exist (x,y) 使得 ax+by=gcd(a,b)

So we can construct it according to the above formulas m0x+m1y=gcd(m0,m1)

通过 ex_gcd 可以求出 gcd(m0,m1) 以及 x,y

于是便有 k0=x×r1−r0gcd(m0,m1)

Bringing back the original formula can be solved X=m0×k0+r0 ,此时 X 的通解为 X′=X+k×lcm(m0,m1) （ k 为一整数,想要让 X′%m0=r0,X′%m1=r1 These two formulas are established at the same time,X The step size for each increment should be lcm(m0,m1)

The above formula can be transformed into ： X′%lcm(m0,m1)=X

So the two equations are merged~

After merging all the equations,输出最小的正整数 X′

Ask about the code k0 modmigcd(M,mi)

a×x0+b×y0=gcd(a,b) 等同于 a×x0+a×bgcd(a,b)k+b×y0−a×bgcd(a,b)k=gcd(a,b)

即 a×(x0+bgcd(a,b)k)+b×(y0−agcd(a,b)k)=gcd(a,b)

通解为 x=x0+bgcd(a,b)k , y=y0−agcd(a,b)k ,其中 k=...−2,−1,0,1,2...

So in all solutions x 的最小正整数解为 (x0+bgcd(a,b))%bgcd(a,b) , y

所以 modmigcd(M,mi) 保证了 k0

AC 代码

       
       #include<iostream>
       
       #include<algorithm>
       
       #include<stdio.h>
       
       #include<string.h>
       
       #include<cmath>
       
       #include<iostream>
       
       using 
       
       namespace 
       
       std;
       
       #include<queue>
       
       #include<map>
       
       #define INF (1<<25)
       
       typedef 
       
       __int64 
       
       LL;
       
       #define maxn 10005
       
       LL 
       
       m[
       
       maxn],
       
       r[
       
       maxn];
       
       int 
       
       n;
       
       LL 
       
       ex_gcd(
       
       LL 
       
       a, 
       
       LL 
       
       b, 
       
       LL 
       
       &
       
       x, 
       
       LL 
       
       &
       
       y)
       
{
       
       LL 
       
       d 
       
       = 
       
       a;
       
       if(
       
       b 
       
       != 
       
       0)
       
    {
       
       d  
       
       = 
       
       ex_gcd(
       
       b, 
       
       a 
       
       % 
       
       b, 
       
       y, 
       
       x);
       
       y 
       
       -= (
       
       a
       
       /
       
       b) 
       
       * 
       
       x;
       
    }
       
       else 
       
       x 
       
       = 
       
       1, 
       
       y 
       
       = 
       
       0;
       
       return 
       
       d;
       
}
       
       LL 
       
       solve()
       
{
       
       LL 
       
       M
       
       =
       
       m[
       
       0],
       
       R
       
       =
       
       r[
       
       0],
       
       gcd,
       
       x,
       
       y;
       
       for(
       
       int 
       
       i
       
       =
       
       1; 
       
       i
       
       <
       
       n; 
       
       i
       
       ++)
       
    {
       
       gcd
       
       =
       
       ex_gcd(
       
       M,
       
       m[
       
       i],
       
       x,
       
       y); 
       
       // Extended Euclidean to find the coefficients x y gcd
       
       if((
       
       r[
       
       i]
       
       -
       
       R)
       
       %
       
       gcd)
       
       return 
       
       -
       
       1;  
       
       // If it is not divisible, there is no solution
       
       LL 
       
       k
       
       =(
       
       r[
       
       i]
       
       -
       
       R)
       
       /
       
       gcd
       
       *
       
       x
       
       %(
       
       m[
       
       i]
       
       /
       
       gcd); 
       
       // 求k0
       
       LL 
       
       X
       
       =
       
       k
       
       *
       
       M
       
       +
       
       R;     
       
       // Substitute back to the original requestX
       
       M
       
       =
       
       M
       
       /
       
       gcd
       
       *
       
       m[
       
       i];   
       
       // M变为lcm
       
       R
       
       =(
       
       X
       
       +
       
       M)
       
       %
       
       M;      
       
       // Rbecomes the smallest at this timeX
       
    }
       
       return 
       
       R;
       
}
       
       int 
       
       main()
       
{
       
       while (
       
       ~scanf(
       
       "%d",
       
       &
       
       n))
       
    {
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       ++
       
       i)
       
       scanf(
       
       "%I64d%I64d", 
       
       &
       
       m[
       
       i], 
       
       &
       
       r[
       
       i]);
       
       printf(
       
       "%I64d\n",
       
       solve());
       
    }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.