博客

题目描述

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

输入描述

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

输出描述

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

样例输入

3 10

样例输出

7

解题思路：

a

x≡ 1( mod b) 等价于 a

x + b*y = 1 (y是倍数)

采用欧几里得算法求解x0,y0；

再根据通解公式：

x = x0 + bt;

y = y0 – at;(t是任意整数)

再若x0<0 ，则一直累加b直到大于0。

(建议先去了解下扩展欧几里得算法,再来看这题！！！)

#include<stdio.h>
void exGcd(int a,int b,int *x,int *y)       //扩展欧几里得(求出x0,y0）  
{
    int t;
    if(b == 0)
    {
        *x = 1;
        *y = 0;
        return ;
    }
    exGcd(b,a%b,x,y);
    t = *x;
    *x = *y;
    *y = t-a/b*(*y);
}

int main()
{
    int a,b;
    int x,y;
    scanf("%d%d",&a,&b);
    exGcd(a,b,&x,&y);
    while(x < 0) x += b;            		//根据通解公式进行累加,找到最小正整数
    printf("%d\n",x);
    return 0;
}