HDU 1576A/B 扩展欧几里得
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1576
题意：
Description
要求(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
思路：设(A/B)%9973 = x,得A/B = 9973y + x,然后A = 9973By + Bx,两边同时取余9973,得Bx + 9973y = n,此时可以用欧几里得求出Bx + 9973y = gcd(B, 9973) = 1的x,y值。两边同时乘以n,即答案为n * x,然后取模保证答案为正数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int extgcd(int a, int b, int &x, int &y)
{
int d = a;
if(b != 0)
{
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}
else x = 1, y = 0;
return d;
}
int main()
{
int t, n, b;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &b);
int x, y;
int g = extgcd(b, 9973, x, y);
printf("%d\n", (x * n % 9973 + 9973) % 9973);
}
return 0;
}
智能推荐
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。