题目链接:uva 10548 - Find the Right Changes
题目大意:给定A,B,C,求x,y,使得xA+yB=C,求有多少种解。
解题思路:拓展欧几里得,保证x,y均大于等于0,确定通解中t的取值。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f;
ll A, B, C;
void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
if (b == 0) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, d, y, x);
y -= (a/b) * x;
}
}
void solve () {
ll d, x, y;
gcd(A, B, d, x, y);
if (C % d) {
printf("Impossible\n");
return;
}
ll up = INF, lower = -INF;
if (B / d > 0)
lower = max(lower, (ll)ceil( (-1.0*x*C) / B) );
else
up = min(up, (ll)floor( (-1.0*x*C) / B) );
if (A / d > 0)
up = min(up, (ll)floor( (1.0*y*C) / A));
else
lower = max(lower, (ll)ceil( (1.0*y*C) / A));
if (up == INF || lower == -INF)
printf("Infinitely many solutions\n");
else if (up < lower)
printf("Impossible\n");
else
printf("%lld\n", up - lower + 1);
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
scanf("%lld%lld%lld", &A, &B, &C);
solve();
}
return 0;
}
分享到:
相关推荐
拓展欧几里得-求解二元一次方程.cpp
用PHP实现欧几里得和拓展欧几里得计算的程序。
此文档是拓展欧几里得的ppt,里面还囊括了费马小定理,逆元,欧拉降幂相关的,可谓应有尽有
算法导论15-1思考题:双调欧几里得旅行商问题,时间复杂度O(N^2)
大数据-算法
OpenCV---基于欧几里得距离计算公式的图像二值化实现.具体的讲解见博客:http://blog.csdn.net/FreeApe/article/details/50409862
大数据-算法
什么是欧几里得算法? 欧几里得算法是求两个整数...二、欧几里得算法The Euclidean Algorithm 欧几里得算法是一种快速找到两个整数的最大公约数GCD的方法,也被称为“辗转相除法”。 三、欧几里得算法第4条规则的证明
matlab开发-QAM的欧几里得距离最小值。基于最小欧氏距离的QAM检测方法
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
matlab_基于DBSCAN算法的欧几里得度量数据聚类matlab仿真_源码
这项工作提出了一种时空的替代几何模型,该模型与当前模型不同,它仅基于欧几里得几何。 在新模型中,伪欧几里德时空被二维欧几里德空间的特定子集代替。 这项工作表明,二维欧几里德空间可以解释已知的相对论效应...
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
正在使用广义欧几里得除法运行计算(520,3344),运算过程如下: 3344 = 6 · 520 + 224 520 = 2 · 224 + 72 224 = 3 · 72 + 8 72 = 9 · 8 + 0 ...拓展欧几里得除法得 s = -45.0,t = 7.0。
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
扩展欧几里得算法求逆元
欧几里得算法的应用 欧几里得算法的应用 欧几里得算法的应用
Python 机器学习 欧几里得距离
欧几里得算法及扩展的欧几里得算法的C++实现。包括.cpp,.exe可执行文件。我的作业。对于密码学和C++初学者有用处,希望对大家有帮助。
欧几里得算法实现,很有用的,一定要支持的哦