#1530 : 分数取模
时间限制: 1000ms
单点时限: 10000ms
内存限制: 256MB
描述
给定三个正整数 a、 b 和 p,满足 b 和 p 互质。这时分数 a / b 除以 p 的余数,即 a / b MOD p 可以定义为 a × b-1 MOD p。
其中b-1 是 b 的逆元,它满足 1 ≤ b-1 < p 且 b × b-1 ≡ 1 MOD p,满足上述条件的 b-1有且仅有一个。
例如 2-1 ≡ 4 MOD 7,因为2 × 4 ≡ 1 MOD 7; 3-1 ≡ 3 MOD 8,因为3 × 3 ≡ 1 MOD 8。
于是我们可以利用b-1求出a / b MOD p,例如: 3 / 2 MOD 7 = 3 × 2-1 MOD 7 = 3 × 4 MOD 7 = 5
给定三个正整数 a、 b 和 p,满足 b 和 p 互质,求 a / b MOD p。
输入
第一行包含3个正整数,a、b 和 p 满足 b 和 p 互质。
对于30%的数据,1 ≤ a, b < p ≤ 100
对于80%的数据,1 ≤ a, b < p ≤ 100000
对于100%的数据,1 ≤ a, b < p ≤ 1000001333
输出
输出 a / b MOD p的值。
- 样例输入
-
3 2 7
样例输出 -
5 分析:a/b MOD p的意思就是(a*b-1)MOD p,这里b-1指的是b关于p的乘法逆元,令x=b-1, 即b*x MOD p=1 ==> b*x=p*y+1 ==> bx+(-py)=1=gcd(b,p),然后用扩展gcd求特解x。 注意:这里b与p互质 摘自维基百科:
模逆元也称为模倒数,或者模逆元。
一a对n之模逆元是指满足以下公式的整数 b
也可以写成以下的式子
整数 a 对模数 n 之模逆元存在的是 a 和 n ,若此模逆元存在,在模数 n 下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。
下面给出扩展gcd求模逆元的代码
#include
long long exgcd(long long a,long long b,long long &x,long long &y){ //求出gcd(a,b)顺带求出一组特解使得ax+by=gcd(a,b) if(b==0) { x=1; y=0; return a; } int r=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return r;}int main(){ long long a,b,p,x,y; scanf("%lld%lld%lld",&a,&b,&p); long long r=exgcd(b,p,x,y); printf("%lld\n",a*((x+p)%p)%p); return 0;}