题意:求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。
思维:(1)逆元+扩展欧几里得算法:满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。当且仅当gcd(k,p) = 1,如果可逆则可定义除法 x/k = x * a mod p
(2)扩展欧几里得算法+递推公式:运用扩展欧几里德算法能解出gcd(a,b)=a*x1+b*y1的x1和y1的值。
(3)数学思维解法:推等式+枚举某数让等式成立。
题目:
要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。
Input
数据的第一行是一个T,表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2 1000 53 87 123456789
Sample Output
7922 6060
AC代码
逆元:为什么要有乘法逆元呢? 当我们要求(a/b) mod p的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元。 我们可以通过求b关于p的乘法逆元k,将a乘上k再模p,即(a*k) mod p。其结果与(a/b) mod p等价。 (A/B)%9973,但由于A很大且gcd(B,9973) = 1),所以我们可以求B的逆元然后 k*B = 1 mod n 然后改写式子 (A/B)%9973 = A % 9973 * k%9973 B的逆元就用扩展欧几里德解 k*B = 1 mod n --> k*B + m*n = 1;
#include<iostream>/**逆元+拓展欧几里得*/
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long int64;
int64 Exgcd(int64 a,int64 b,int64 &x,int64 &y)
{
if(b == 0)
{
x = 1,y = 0;
return a;
}
else
{
int64 r = Exgcd(b,a%b,x,y);
int64 temp = x;
x = y, y = temp - a/b*y;
return r;
}
}
int main()
{
int t;
int64 n,b = 9973,B,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d",&n,&B);
int64 d = Exgcd(B,b,x,y);
b = b / d;
x = x / d ;
x = (x % b + b) % b;/*求a最小正整数逆元x=x0+(a/gcd)*t*/
printf("%I64d\n",(n%9973 * x%9973)%9973);/*x为n的逆元*/
}
return 0;
}
拓展欧几里得:
根据题目我们知道: n=A%9973,则n=A-A/9973*9973。又A/B=x,则A=Bx。所以Bx-A/9973*9973=n。即Bx-9973y=n。 在这里我们知道只要求出x的值就能算出x%9973的值,也就是(A/B)%9973的值。 利用扩展欧几里德算法可求出gcd(B,9973)=Bx1+9973y1=1的x1。题中说gcd(B,9973)=1;所以等式两边 同乘以n,得B(n*x1)-9973(-n*y1)=n。可知n*x1就是B*x-9973*y=n的解了!!!即x=n*x1。 在扩展欧几里得算法中得到的x可能为负值,所以还需要x=(x%9973+9973)%9973。
#include<cstdio>/**推等式+拓展欧几里得*/
#include<cstring>
void extgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return ;
}
else
{
extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
}
int main()
{
int t,n,b,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&b);
extgcd(b,9973,x,y);
x*=n;
x=(x%9973+9973)%9973;
printf("%d\n",x);
}
return 0;
}
数学思维解法: 思路:设X=(A/B)%9973 因为n=A%9973,所以A=k*9973+n (k为一常数) 又因为X=(A/B)%9973,所以A/B=d*9973+X (d为一常数) 两边同乘以B,得:A=B*d*9973+B*X 即B*d*9973+B*X=k*9973+n 移项得: B*d*9973+B*X-n=k*9973 所以题意转为 只要满足(B*X-n)%9973=0,X即为要求的结果。n的值知道,B的值知道,又因为x的取 值范围是0到9972,因此枚举x的值即可,满足条件的就是答案。
#include<cstdio>/**推等式+枚举某数让等式成立*/
int main()
{
int n,a,i,t;
long long b;
scanf("%d",&t);
while(t--)
{
scanf("%d%lld",&n,&b);
for(i=0;i<9973;++i)
{
if((b*i-n)%9973==0)
break;
}
printf("%d\n",i);
}
return 0;
}