KIDx 的解题报告
题目链接:http://poj.org/problem?id=2142
不懂扩展欧几里得请先参照这里:
http://972169909-qq-com.iteye.com/blog/1140914
题意:输入3个数,前2个是砝码的种类,问各要多少个才能称出第三个数出来【同时要使2个答案之和最小】
#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define LL __int64
LL gcd (LL a, LL b)
{
return b ? gcd (b, a%b) : a;
}
LL Egcd (LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
LL d = Egcd (b, a%b, x, y);
LL tp = x;
x = y;
y = tp - a/b*y;
return d;
}
int main()
{
LL a, b, n, x, y, vx, vy, d;
while (scanf ("%I64d%I64d%I64d", &a, &b, &n), (a||b||n))
{
d = gcd (a, b);
a /= d;
b /= d;
n /= d;
Egcd (a, b, x, y);
/**********①令y是最小正整数解**********/
vy = y*n;
vy = (vy % a + a) % a;
vx = (n-b*vy) / a;
if (vx < 0) //题目要的是使用砝码的个数,所以要正整数
vx = -vx;
/**********②令x是最小正整数解**********/
x *= n;
x = (x % b + b) % b;
y = (n-a*x) / b;
if (y < 0) //同理
y = -y;
/**********③使得和最小**********/
if (x + y < vx + vy)
vx = x, vy = y;
printf ("%I64d %I64d\n", vx, vy);
}
return 0;
}
分享到:
相关推荐
扩展欧几里得算法求逆元
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
扩展欧几里得详解证明,里面没有例题,详细请看统一标题html的文档
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
本算法实现了用扩展欧几里得的方法求最大公因子和模逆元的方法,可以直接运行。
在编写扩展欧几里得算法的前提下,计算了两个数的最大公因数,判断两数是否互素。
利用扩展欧几里得方法,进行快速的计算C(n,m)%P;
扩展欧几里得 代码 详解 证明 例题
matlab的M函数文件,附带了函数的使用说明了
以扩展欧式定理为基础,编程实现: 输入两个数, 判断:是否互素 分别算出:GCD;二者的互模逆。 考虑负数和大数(如256位)等情况。
ACM数论基础知识入门之扩展欧几里得算法
密码学考试复习(关于快速指数算法和扩展欧几里得求逆元),之前考试自己整理的,今天又要学了。里面的算法还能看,还整理的比较透彻当时。备用了留在这。不知道为什么之前上传的xmind一点就跳转到别的页面了,这次...
封装好的扩展欧几里得、模幂运算及欧拉函数算法代码
扩展欧几里得算法的实现,帮助新手进行学习。
介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
35扩展欧几里得算法1
包括完整的c语言实现扩展的欧几里得算法代码截图和相关代码说明以及程序截图