nyoj1235A/B Problem逆元
发布日期:2021-06-29 11:13:57
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月03日 13时30分31秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
基于 Hystrix 高并发服务限流第 5 篇 —— Hystrix 监控
2019-04-29
Eureka 如何快速的、优雅的停止某个微服务
2019-04-29
Eureka 实现安全认证
2019-04-29
Nginx 反向代理、负载均衡配置、Location正则表达式
2019-04-29
SpringBoot + WebSocket 实现前后端的收发消息
2019-04-29
SpringBoot 整合 JWT 实现统一认证
2019-04-29
SpringBoot 使用 CompletableFuture 实现非阻塞异步编程
2019-04-29
即刻就业:本科毕业如何快速高薪就业?
2019-04-29
JAVA中的浮点数与二进制
2019-04-29
JAVA笔记(二)--Java初始
2019-04-29
JAVA笔记(三)--变量及运算符
2019-04-29
JAVA笔记(四)--三大结构语句
2019-04-29
JAVA语言基础(五)--数组
2019-04-29
JAVA项目案例详解带代码
2019-04-29
JAVA九种排序算法详解
2019-04-29
JAVA笔记(六)面向对象--类和对象
2019-04-29
JAVA笔记(十一)面向对象--多态
2019-04-29