HDU 1576 A/B(欧几里德算法延伸)
2024-10-18 05:10:40
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1576
题目:
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)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060
/*
问题
给出n(0 <= n < 9973)和B(1 <= B <= 10^9),计算(A/B)%9973
其中n=A%9973,A必能被B整除,且gcd(B,9973) = 1 解题思路
设X=(A/B)%9973,则A/B=K*9973+X(K为正整数)
即A=K*9973*B+X*B 又n=A%9973,则A=p*9973+n 结合两式可得 p*9973+n=K*9973*B+X*B
移项可得 p*9973-K*9973*B=X*B-n
即9973*(p-K*B)=X*B-n
显然左边对9973取余等于0,那么0=(X*B-n)%9973
此时直接枚举X取值即可,另外注意到X*B可能对超出int范围,需要用到同余运算,当然直接将其转换为long long类型也可。
(a-b)%n=((a%n)-(b%n)+n)%n
(a*b)%n=(a%n)*(b%n)%n
故(x*B-n)%9973=( ((X%9973)*(B%9973)%9973) -(n%9973)+9973 )%9973
*/ #include<cstdio> int main()
{
int t,n,X;
long long B;
scanf("%d",&t);
while(t--){
scanf("%d%lld",&n,&B);
for(X=;;X++){
if((((X%)*(B%)%) - (n%)+)% == ){
printf("%d\n",X);
break;
}
}
}
return ;
}
最新文章
- java.lang.ArrayIndexOutOfBoundsException: 1
- 《JavaScript权威指南》学习笔记 第二天 下好一盘大棋
- 李洪强iOS开发支付集成之银联支付
- 贴心小技能——纯CSS实现的帮助提示
- UVa 1151 (枚举 + MST) Buy or Build
- hellogcc -100GDB技巧
- 在CGridView调用CJuiDialog的弹出层
- 开源Math.NET基础数学类库使用(13)C#实现其他随机数生成器
- javascript中数组常用方法总结
- RAP在Linux 上的部署
- Shuffle过程的简单介绍
- jsbin本地部署
- WEB服务器,TOMCAT和servlet之间的关系
- VS2015 类模板保存位置
- Centos7安装jdk1.8并查找jdk安装目录
- 设计模式之Factory(工厂)(转)
- AttributeError: &#39;WebDriver&#39; object has no attribute &#39;switchTo&#39;
- Waymo在美国推出自动驾驶汽车共享服务
- Java设计模式应用——策略模式
- eclipse初始设置
热门文章
- ASP.NET Web API 框架研究 Self Host模式下的消息处理管道
- ElementTriArgyris
- 机器学习实战-ch2-有标签的聚类算法
- Winform下的Combox根据值来选中项
- cad2016卸载/安装失败/如何彻底卸载清除干净cad2016注册表和文件的方法
- select2插件使用小记2 - 多选联动 - 笔记
- 开发ASP.NET MVC 开发名片二维码生成工具 (原创)
- WebDriver高级应用实例(7)
- sql server 2012 打开提示无效的许可证数据。需要重新安装
- 十分钟内在Ubuntu系统上搭建Mono开发环境(Mono软件Ubuntu系统国内镜像源、Mono国内镜像源)