hdoj1576A/B【扩展欧几里得】

2023-09-23 66 0

A/B

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3349    Accepted Submission(s): 2543

Problem 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

Author
xhd

Source
HDU 2007-1 Programming Contest

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
void exgcd(long long a,long long b,long long &x,long long &y){if(b==0){x=1;y=0;}else {exgcd(b,a%b,y,x);y-=(a/b)*x;}
}
int main()
{//A=B*X=n+9973*y B*X-9973*y=n;long long n,b,t;scanf("%lld",&t);while(t--){scanf("%lld%lld",&n,&b);long long x,y;exgcd(b,9973,x,y);x=(x*n)%9973;if(x<0)x+=9973;printf("%lld\n",x);}return 0;
}
代码编程
赞赏

相关文章

数商云食品行业解决方案:新技术加持食品行业,为企业快速发展提供有力支撑
星期零斩获2021新消费领域“投资界50强企业”和“中国食品工业创新品牌”奖项
2022-2028年中国食品产业园区行业市场运行格局及发展策略分析报告
工业互联网业务知识
劲牌公司荣获2020年度“中国食品工业协会科学技术奖”特等奖
面试3_:不修改数组找出重复的数字