HDUOJ----专题训练C

Problem C

Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 6   Accepted Submission(s) : 5

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

2 1000 53 87 123456789

Sample Output

7922 6060

此题做法多样....一种是用欧几里得扩展来做,另一种是暴力来做...

先来讲讲欧几里得扩展的吧!! 又题目的意思不难理解:由于 n=a%9973,所以A=k*9973+n与之等价...

 由于gcd(b,9973)=1;也就是 b和9973的公约数恒定为1。。。。

而且 A=w*b。。。(需要说明的一点是,w,k,都是为未知数)

也就是有这么一个等式    w*b=k*9973+n (mod 9973) 恒定成立。。。

然后就不能化解成为 w*b+x*9973=n-----》构造出了  a*x+b*y=c这种模式....

然后就可以求解了啊!( 详细说明请看,第一个欧几里得扩展题目,那里有些关于欧几里得扩展的几个定理) 贴下代码....

 1 #include<iostream>
 2 using namespace std;
 3 int x,y,q;
 4 void exgcd(int a,int b)
 5 {
 6   if(b==0)
 7   {
 8    x=1,y=0,q=a;
 9   }
10   else
11   {
12       exgcd(b,a%b);
13       int temp=x;
14       x=y,y=temp-a/b*y;
15   }
16 }
17 int main()
18 {
19     int n,b,t;
20     cin>>t;
21     while(t--)
22     {  
23         cin>>n>>b;
24         exgcd(b,9973);
25         q;
26         int temp=9973/q;
27         cout<<((n/q*x%temp+temp)%temp)<<endl;
28     }
29     return 0;
30 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

hdu 3367(Pseudoforest ) (最大生成树)

Pseudoforest Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/6553...

39240
来自专栏ml

hdu----(1677)Nested Dolls(DP/LIS(二维))

Nested Dolls Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

32660
来自专栏小樱的经验随笔

POJ 1163 The Triangle【dp+杨辉三角加强版(递归)】

The Triangle Time Limit: 1000MS Memory Limit: 10000K Total Submissions: ...

28670
来自专栏智能计算时代

在今天的企业环境如何使用机器学习

One of the latest trends in the world of technology and engineering is “machine ...

33550
来自专栏算法修养

POJ 1015 Jury Compromise(双塔DP)

Jury Compromise Time Limit: 1000MS Memory Limit: 65536K Total Submissio...

29040
来自专栏wym

Starship Troopers(树状dp) hdu1011

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Ot...

14410
来自专栏ml

hdu----(5023)A Corrupt Mayor's Performance Art(线段树区间更新以及区间查询)

A Corrupt Mayor's Performance Art Time Limit: 2000/1000 MS (Java/Others)    Memo...

36390
来自专栏ml

HDUOJ Children’s Queue

Children’s Queue Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3...

28590
来自专栏算法修养

POJ-1179 Polygon (动态规划)

Polygon Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 5293...

32980
来自专栏ml

poj-----(2528)Mayor's posters(线段树区间更新及区间统计+离散化)

Mayor's posters Time Limit: 1000MS Memory Limit: 65536K Total Submission...

28240

扫码关注云+社区

领取腾讯云代金券