同余方程

ゝ一纸荒年。 2021-12-19 17:51 297阅读 0赞

## 描述 ##

求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。

## 格式 ##

### 输入格式 ###

输入只有一行，包含两个正整数a, b，用一个空格隔开。

### 输出格式 ###

输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证一定有解。

## 样例1 ##

### 样例输入1\[复制\] ###

>     3 10

### 样例输出1\[复制\] ###

>     7

## 限制 ##

每个测试点1s

## 提示 ##

对于40%的数据，2 ≤b≤ 1,000；  
对于60%的数据，2 ≤b≤ 50,000,000；  
对于100%的数据，2 ≤a, b≤ 2,000,000,000。

## 来源 ##

Noip2012提高组复赛Day2T1

\--------------------------------------------------

就是求解一个方程：ax=by+1

从贴吧学了一种解题方法，非常神奇

假设方程是

7x=10y+1　　　x=3;y=2

↓　　　　　　　 ↑

7x=3y+1　　　 x=1;y=2

↓　　　　　　　　↑

x=3y+1　　　　x=1;y=0;

当a=1时就令 x=1;y=0

所以答案就是x=3，y=2

再来一个

153x=542y+1 　　 x=333;y=94

↓　　　　　　　 ↑

153x=83y+1　　　 x=51;y=94

↓　　　　　　　　↑

70x=83y+1　　　 x=51; y=43

↓　　　　　　　 ↑

70x=13y+1　　　 x=8; y=43

↓　　　　　　　　↑

5x=13y+1　　　　 x=8; y=3

↓　　　　　　　　↑

5x=3y+1　　　　　x=2; y=3

↓　　　　　　　　↑

2x=3y+1　　　　　x=2；y=1

↓　　　　　　　　↑

2x=y+1　　　　　 x=1；y=1

当b=1时，令　　　　x=1；y=1

所以答案是x=333;y=94;

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 var
     2   x,y,a,b:int64;
     3 procedure egcd(a,b:int64;  var x,y:int64);
     4 begin
     5   if a=1 then
     6     begin
     7       x:=1;
     8       y:=0;
     9       exit;
    10     end;
    11   if b=1 then
    12     begin
    13       x:=1;
    14       y:=a*x-1;
    15       exit
    16     end;
    17   if a<b then
    18     begin
    19       egcd(a,b mod a,x,y);
    20       x:=(b*y+1)div a;
    21     end
    22   else
    23     begin
    24       egcd(a mod b,b,x,y);
    25       y:=(a*x-1)div b;
    26     end;
    27 end;
    28 begin
    29   read(a,b);
    30   egcd(a,b,x,y);
    31   writeln(x);
    32 end.

转载于:https://www.cnblogs.com/zjhl2/p/3935784.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211219/7573c1c414f24bad83397db13b1370ce.png