扩展欧几里得+具体例子A|扩展欧几里得+具体例子A / B.
扩展欧几里得算法
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展，除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时，我们都会提到一个非常基本的事实：给予二整数a与b，必存在有整数x与y使得ax+by=gcd（a，b）。有两个数a，b，对它们进行辗转相除法，可得它们的最大公约数————这是众所周知的。然后收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd（a，b）的整数解。
【扩展欧几里得+具体例子A|扩展欧几里得+具体例子A / B.】已知整数a、b扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式ax+by=gcd(a,b)
如果a是负数，可以把问题转化成
文章图片
具体模板代码如下
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{//推理，终止条件1
x=1;
y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=y;
y=x-(a/b)*y;
x=t;
return r;
//最大公约数
}A/B
要求（A / B）％9973，但由于A很大，我们只给出n（n = A％9973）（我们给定的A必能被B整除，且gcd（B，9973）= 1）。
输入
数据的第一行是一个T，表示有T组数据。
每组数据有两个数n（0 <= n <9973）和B（1 <= B <= 10 ^ 9）。
产量
对应每组数据输出（A / B）％9973。
样本输入
2 1000 53 87 123456789
样本输出
7922 6060
由题意可以知道n=A%9973，设 x1=A/B，得A=B*x1，又由gcd（B,9973）=1，由扩展欧几里得得出 Bx+9973y=1
这一题的关键就是求出A/B的值 也就是x1的值 可以先知道A=B*x1
对于Bx+9973y=1两边同时乘以n得到 B*x*n+9973*y*n=n可以得到 A=B*x1=B*n*x因此可以的出x1=n*x。
因此可以用扩展欧几里得来求出对应的解x1然后进行对9973取余数 但是会有负值
负值跟题中的意思不符合 因此可以用一个公式(x%9973+9973)%9973
#include
using namespace std;
const int mod=9973;
void cnm(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return;
}
else
{
cnm(b,a%b,x,y);
int tmp=x;
x=y;
y=tmp-a/b*y;
}
}
int main()
{
int t,n,b,x,y,tmp;
cin>>t;
while(t--)
{
cin>>n>>b;
cnm(b,mod,x,y);
x*=n;
tmp=(x%mod+mod)%mod;
cout< 文章图片
推荐阅读
- Unity和Android通信系列文章2——扩展UnityPlayerActivity
- PHP|PHP 扩展开发检测清单（扩展开发必读）
- 知识扩展-SQL查询基础
- laravel|laravel 添加扩展包步骤
- bgo:|bgo: 具备扩展性的 go 程序构建工具
- Centos8中如何更改文件夹中多个文件的扩展名
- chrome插件教程2-一个简单的chrome扩展
- 为BFE编写扩展插件(1)|为BFE编写扩展插件(1) – 回调点
- 学习PHP中的高精度计时器HRTime扩展
- 欧几里得算法