hdu 1576 A/B(求逆元模板题)

2024-04-05 21:18

文章标签 模板 hdu 逆元 1576

本文主要是介绍hdu 1576 A/B(求逆元模板题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ACM国际大学生程序设计竞赛全球总决赛

A/B

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7034 Accepted Submission(s): 5595

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

Author

xhd

Source

HDU 2007-1 Programming Contest

Recommend

linle | We have carefully selected several similar problems for you: 1788 1211 1787 1299 1573

分析：求逆元裸题，(a/b)%9973 , b*x==1%9973(同余) ---->(a/b*b*x)=(a*x)%9973

有两种方法，一是利用费马小定理a^(p-1)==1%p(同余，a与p互质)，但是要求p为素数，这里9973为素数；二是利用扩展欧几里得算法 ax+by=1，其中a，b互质，即ax==1%b（同余），因为(m/a)%b = ( m/a*a*x)%b = 1;所以x可以作为a的逆元，同理y是b的逆元，这里不要求模数为质数，拓展欧几里得算法中是是利用辗转相除逆向地递推出x,y的值，此处不做详解，具体过程就是解一个同余方程。

代码一：（费马小定理）

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define mod 9973ll inv(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;
}int main(){int t,n,b;cin>>t;while(t--){cin>>n>>b;ll invb=inv(b,mod-2);cout<<n*invb%mod<<endl;}
}

代码二：（扩展欧几里得）

#include<iostream>
using namespace std;
#define ll long long
#define mod 9973void exgcd(ll a,ll b,ll &x,ll &y){if(!b) {x=1,y=0;return ;}else {exgcd(b,a%b,y,x);y-=a/b*x;}
}int main(){int t,n,b;cin>>t;while(t--){cin>>n>>b;ll x,y;exgcd(b,mod,x,y);cout<<n*((x+mod)%mod)%mod<<endl;}
}

这篇关于hdu 1576 A/B(求逆元模板题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！