问题 B: 同余方程（Day 2）

问题 B: 同余方程（Day 2）

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 16
[提交][状态][讨论版][命题人:外部导入][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1703&pid=1

题目描述

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

输入

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

数据规模：

对于40%的数据，2≤b≤1,000；

对于60%的数据，2≤b≤50,000,000；

对于100%的数据，2≤a, b≤2,000,000,000。

输出

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

样例输入

3 10

样例输出

7

思路：两种方法，求数论倒数（逆元），欧拉定理加快速幂，或者用辗转相除法（扩展欧几里得定理加裴蜀定理）这两个都行，时间复杂度应该是辗转相除法低很多。。但是代码复杂一点。

方法一：欧拉定理加快速幂

代码：

#include<bits/stdc++.h>

using namespace std;

#define maxn 10000

#define ll long long

#define maxn 1000005

#define INF 0x3f3f3f3f

int m, p[maxn], c[maxn];

int all = 0;

void divide(int n)//质因数分解

{

    m = 0;

    all = 0;

    for (int i = 2; i*i <= n; i++)

    {

         if (n%i == 0)

         {

             p[++m] = i, c[m] = 0;

             while (n%i == 0)n /= i, c[m]++;

         }

    }

    if (n > 1)

         p[++m] = n, c[m] = 1;//p存储y所含的质因数，c存储那个质因数的个数

}

ll quickpow(ll a, ll b, ll mod)//快速幂

{

    if (b == 1)return a;

    else

    {

         if (b % 2 == 0)

         {

             ll t = quickpow(a, b / 2, mod);

             return t * t%mod;

         }

         else

         {

             ll t = quickpow(a, b / 2, mod);

             t = t * t%mod;

             return t * a%mod;

         }

    }

}

int main()

{

    ll x, y;

    cin >> x >> y;

    divide(y);//质因数分解

    double oula = y;//记录y的欧拉函数值

    for (int i = 1; i <= m; i++)//求y的欧拉函数值

    {

         oula *= (1 - 1.0/ p[i]);//欧拉函数

    }

    cout << quickpow(x, oula - 1, y);//用欧拉定理求逆元

}

方法二：辗转相除法（扩展欧几里得定理加裴蜀定理）

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

//扩展欧几里得定理+裴蜀定理，求解ax+by=d的一组解（x,y），d=gcd（a,b）

void exgcd(ll a, ll b, ll &d, ll &x, ll &y)

{

    ll t;

    if (b == 0)

    {

         d = a; x = 1; y = 0;

    }

    else

    {

         exgcd(b, a%b, d, x, y);//利用辗转相除法（a,b）=(a,a-b)=(a,a%b)

         t = x; x = y; y = t - (a / b)*y;

    }

}

int main()

{

    ll a, b;

    cin >> a >> b;

    ll d, x, y;

    exgcd(a, b, d, x, y);

    //现在算出了d,x,y

    //因为ax+by=d，两边同时模b，ax≡d(mod b)

    //a(x/d)≡1(mod b)

    //因为答案要求正整数，所以直接算a(x/d)+ab≡1(mod b),a(x/d+b)≡1(mod b),答案求的就是(x/d+b)%b

    cout << (x / d + b) % b;

}