nyoj1235A/B Problem逆元
发布日期:2021-06-29 11:13:57
浏览次数:4
分类:技术文章
本文共 1279 字,大约阅读时间需要 4 分钟。
nyoj1235A/B Problem
时间限制:1000 ms | 内存限制:65535 KB 难度:3 描述
已知:
1. n = (A % 9973);2. gcd(B, 9973) = 1;
计算:
(A / B) % 9973
输入
数据的第一行是一个T,表示有T组数据. 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9). 输出 对应每组数据输出(A / B) % 9973. 样例输入 2 1000 53 87 123456789 样例输出 7922 6060
#includeconst int mod = 9973;//(A / B) % mod;//n = A % mod;//b为B关于mod的逆元 //b = B^(mod-2);//(A / B) % mod = (A * b) % mod = (A%mod * b%mod) % mod = (n * b%mod) % mod //https://www.cnblogs.com/linyujun/p/5194184.html//https://www.cnblogs.com/zzqc/p/7192436.html //http://blog.csdn.net/f_zyj/article/details/71156809void extendGcd(long long a, long long b, long long * s, long long * t);long long modReverse(long long a, long long n);int main() { int times; long long n, B; scanf("%d", ×); while (times--) { scanf("%lld%lld", &n, &B); long long b = modReverse(B, mod); printf("%d\n", (n * b) % mod); } return 0;}void extendGcd(long long a, long long b, long long * s, long long * t) { if (b == 0) { *s = 1, *t = 0; }else { long long next_s, next_t; extendGcd(b, a % b, &next_s, &next_t); *s = next_t, *t = next_s - a/b * next_t; }}long long modReverse(long long a, long long n) { //a与n互质时,才存在a关于n逆元 long long s, t; extendGcd(a, n, &s, &t); return (s + n) % n;//防止s可能为负数}
转载地址:https://blog.csdn.net/ZWHSOUL/article/details/79516980 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月21日 22时31分37秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一文读懂全系列树莓派!
2019-04-29
自制一个害羞的口罩,见人就闭嘴,戴着可以喝奶茶
2019-04-29
聊聊我是如何编程入门的
2019-04-29
J-Link该如何升级固件?
2019-04-29
从电子垃圾中提炼黄金,可以!!!
2019-04-29
知乎大神深入解析:单片机晶振脚原理是什么?
2019-04-29
电容有17种?看看详细介绍!
2019-04-29
如何准备电赛?19年电赛经验总结!
2019-04-29
蓝牙:为啥叫“蓝”牙,不叫“白”牙?
2019-04-29
干货 | 如何系统学习 C 语言?
2019-04-29
多层PCB内部长啥样? 3D大图解析高端PCB板的设计工艺
2019-04-29
鸿蒙2.0都来了,快搭个环境玩起来吧!
2019-04-29
PCB散热的10种方法!
2019-04-29
值得收藏!268条PCB layout设计规范
2019-04-29
Keil升级了,Keil Studio 来了!
2019-04-29
关于RS-485总线,这篇很详细
2019-04-29
关于2021年电赛的一些想法,看到就是赚到!
2019-04-29
教你一秒分辨真假芯片!
2019-04-29
抽奖 | 送STM32开发板
2019-04-29
光立方,永远的神!
2019-04-29