问题 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;
}