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
Sample Output
7922
6060
思路:扩展欧几里得算法的应用
AC代码:
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#define N 9973
using namespace std;
void _gcd(int a,int b,int &x1,int &y1)
{
if(!b) x1=1,y1=0;
else
{
_gcd(b,a%b,x1,y1);
int temp=x1;
x1=y1;
y1=temp-a/b*x1;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int a,c;
scanf("%d%d",&c,&a);
int b=9973;
int x1,y1;
_gcd(a,b,x1,y1);
printf("%d\n",((x1%N)*(c%N)%N+N)%N);
}return 0;
}
分享到:
相关推荐
动态规划:http://acm.zju.edu.cn/forum/viewtopic.php?t=69 搜索:http://acm.zju.edu.cn/forum/viewtopic.php?t=67 数论:http://acm.zju.edu.cn/forum/viewtopic.php?t=66 几何:...
浙江大学在线题库:http://acm.zju.edu.cn/problems.php 浙江工业大学在线题库:http://acm.zjut.edu.cn 衡阳市第八中学信息学奥赛论坛&zju译题站:http://61.187.179.132:82/ UVA在线题库:...
ACM大量习题题库 现在网上有许多题库,大多是可以在线评测,所以叫做Online Judge。除了USACO是为IOI准备外,其余几乎全 部是大学的ACM竞赛题库。 USACO http://ace.delos.com/usacogate 美国著名在线题库,专门为...
Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem ...
Hdu 1020解题报告,http://acm.hdu.edu.cn/showproblem.php?pid=1020
In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign ...
http://acm.hdu.edu.cn/showproblem.php?pid=2020 绝对值排序 txt格式
zju 1048 Financial Managementhttp://acm.zju.edu.cn/show_problem.php?pid=1048
3、林杰博客说明:http://linjie.org/2015/08/06/amr%E6%A0%BC%E5%BC%8F%E8%BD%ACmp3%E6%A0%BC%E5%BC%8F-%E5%AE%8C%E7%BE%8E%E8%A7%A3%E5%86%B3Linux%E4%B8%8B%E8%BD%AC%E6%8D%A20K%E9%97%AE%E9%A2%98/
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
D:\acm\ACM函数整理_ACM模板.pdf
ACM3025.pkl
408复试刷题 这个项目是我在2021年考研时的刷题集锦,其中包括王道机试指南第二版以及杭电OJ,前期用的C语言,后续改用C++,感谢作者炉灰 ...例题2.5 叠筐 http://acm.hdu.edu.cn/showproblem.php?pid=2
TagRec won the best poster award @ Hypertext 2014 (HT'14) conference: http://ht.acm.org/ht2014/index.php?awards.poster TagRec is also a main part of the recommender systems in the Layers project ...
(我现在主要在CSDN上整理计算机安全、软件工程(可信软件)、系统及通信方面的论文及相关理论书籍,如果对这方面内容感兴趣,可以访问:http://qysh123.download.csdn.net/ 查看我上传的所有资料。内容比较多,需要...
杭电hdu acm资料所用杭电的acm题
下面来自:http://acm.hdu.edu.cn/forum/read.php?tid=528&keyword=Catalan|numbers catalan numbers可以用在以下方面: 1. the number of ways a polygon with n+2 sides can be cut into n triangles 2.the number...
/Users/fangchuxi/Desktop/IEEE:ACM/视频流 李雅普诺夫/基于边缘的视频分析的自适应配置选择和带宽分配.md
ACM HDU题目分类,我自己总结的大概只有十来个吧
几个程序设计的训练网站给大家,供大家参考! http://poj.org/ 北大的,比较难 http://acm.hdu.edu.cn/ 杭电的,相对容易 http://cm2prod.baylor.edu/welcome.icpc ACM/ICPC官方网站