noip2012 同余方程

1200 同余方程

2012年NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

3 10

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【数据范围】对于 40% 的数据， 2 ≤b≤ 1,000 ；对于 60% 的数据， 2 ≤b≤ 50,000,000 对于 100% 的数据， 2 ≤a, b≤ 2,000,000,000

分析：

记得之前做过这道题，很早的时候呢.那时完全就是“借鉴”的，现在终于知道为什么这么做了.首先可以考虑暴力……不过只能得一部分分，然后我们将式子变形. ax ≡ 1 (mod b) ax = 1 + by ax – by = 1. 其实这个方程就是让我们求a的逆.有没有解取决于gcd(a,b)是否为1.当然题目保证了有解，就不必担心，然后套用扩展欧几里得算法的模板，得出一个解x,y.这个解不一定是最小的正整数解.假设这组解为x1,y1,另外一组解为x2,y2.可以的知道ax1 + by1 = ax2 + by2 a(x1-x2) = b(y2-y1)我们同时除以gcd(a,b),可以得到x2 = (x1 + b’) y2 = (y1 – a’) 对于任意的其他解x0,y0.

X0 = (x1 + kb’),y0 = (y1 – ka’).如何得到最小解呢？对于x而言,mod一个b即可，对于y而言，mod一个a即可，但是不能保证是不是正数，这个时候加一个b’即可，因为已经是最小解了，加了一个b’一定是正数，问题就解决了.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

long long a, b, x, y;

void god(long long a, long long b, long long &x, long long &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return;
    }
    god(b, a%b, x, y);
    int t = x;
    x = y;
    y = t - a / b*y;
}

int main()
{
    scanf("%lld%lld", &a, &b);
    god(a, b, x, y);
    x = (x % b + b) % b;
    printf("%lld
", x);

    return 0;
}