hdu 1576 A/B (求逆元)
2024-10-20 08:24:05
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
1000 53
87 123456789
Sample Output
7922
6060
6060
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define LL __int64
const int maxn = 1e3 + ;
const int mo = ;
using namespace std; void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if(!b) {d = a; x = ; y = ;}
else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }
} LL mo_reve(LL a, LL n)
{
LL x, y;
LL d;
exgcd(a, n, d, x, y);
if(d==) return (x%n+n)%n;
else return -;
} int main()
{
int t, n, b;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &b);
int x = mo_reve(b, mo);
printf("%d\n", n*x%mo);
}
return ;
}
最新文章
- Ext JS 4 新特性2:配置项属性(config)之二
- Shader预处理宏、内置状态变量、多版本编译等
- linux 鼠标中键粘帖功能?!!
- php 文件上传一例简单代码
- linux下mysql的表名问题
- meta 属性
- MYSQL 日志文件路径错误 1067错误
- discuz用户登录不响应,提示nginx gateway timeout解决方法
- Spring HTTP状态码枚举值对照表
- Ubuntu: 安装自带的中文输入法
- Properties (25)
- Android-Binder原理浅析
- 使用C#和HtmlAgilityPack解析HTML
- vs警告 当前源代码跟内置的版本不一致解决办法
- 数据库如何创建视图create view
- Windows环境下使用Apache+mod
- 详解RocketMQ中的consumer
- [HDU-4825] Xor-Sum (01字典树)
- E20170404-gg
- POJ 3013 【需要一点点思维...】【乘法分配率】
热门文章
- SrpingCloud 之SrpingCloud config分布式配置中心实时刷新
- Idea 包名按树形结构展示
- java入门了解08
- 关于jvm中的常量池和String.intern()理解
- SQL2005 2008配置错误,无法识别的配置节 system.serviceModel machine.config配置文件有问题
- JS使用模板快速填充HTML控件数据
- 我理解的关于Vue.nextTick()的正确使用
- Mybatis中collection与association的区别
- Selenium-免登录的实现
- Idea_学习_01_Idea激活