免费行情软件网站直播,济南高端建站,上海手机网站建设,西部数码网站管理助手 mysql题目描述 题目分析 由于两只青蛙都在跳跃导致变量多#xff0c;不妨采用物理题中的相对运动思想#xff0c;设青蛙A不动#xff0c;青蛙B每次跳米#xff0c;两只青蛙的距离为米。正常来说#xff0c;只要模拟青蛙B与青蛙A的相对运动过程#xff0c;最终当青蛙B与青蛙A距…题目描述 题目分析 由于两只青蛙都在跳跃导致变量多不妨采用物理题中的相对运动思想设青蛙A不动青蛙B每次跳米两只青蛙的距离为米。正常来说只要模拟青蛙B与青蛙A的相对运动过程最终当青蛙B与青蛙A距离为0时即可求得总跳跃次数。但是难点在于数据量大按部就班的模拟将会超时。 由于这是一道有关整数和环的数学题考虑使用扩展欧几里得算法求解。现直接假设一只青蛙静止另一只青蛙每次位移为总跳跃次数为一圈长度为跳跃的圈数为青蛙间的距离为。则题目满足方程。显然要使方程有整数解必须满足的条件是必须是 和 的最大公约数的倍数即。这可以通过贝祖定理证明。 接下来的难点是求出最小跳跃次数。根据拓展欧几里得算法已经得到了方程的一组特解但这不一定是最优解根据线性同余方程的通解公式 只需让该特解模除即可求出跳跃次数在间的最小正整数解。 提交后有一处测试点有误经检查原来在exgcd算法中如果两个参数存在负数输出的最大公因数也可能是负数。这并不影响所得特解的正确性但在求最小正解的时候需要采取措施让取模后的结果转变为正数。 我的代码
#include iostream
#include algorithm
using namespace std;
typedef long long ll;// 扩展欧几里得算法
ll extgcd(ll a, ll b, ll x, ll y) {if (b 0) {x 1;y 0;return a;}ll d extgcd(b, a % b, y, x);y - (a / b) * x;return d;
}int main() {ll x, y, m, n, L;cin x y m n L;ll a n - m; // 移项后得到 a n - mll b x - y; // 常数项 b x - yll l L; // 模数为 Lll x0, y0;ll d extgcd(a, l, x0, y0); // 使用扩展欧几里得求解if (b % d ! 0) {cout Impossible endl;}else {// 存在解的情况求最小非负整数解ll k (x0 * (b / d)) % (l / d); //其中x0*(b/d)为一个方程的特解if (k 0) {if (l / d 0) {k l / d; // 保证 k 为非负}else {k - l / d; // 保证 k 为非负}}cout k endl;}return 0;
}由于扩展欧几里得算法参数使用了引用导致逻辑相对更难理解我利用原本欧几里得算法的数学递推逻辑修改为一下函数程序可以成功运行
ll x_0;
ll y_0;
ll x_1;
ll y_1;
ll extgcd(ll a, ll b) {ll d a;if (b ! 0) {d extgcd(b, a % b);x_0 y_1;y_0 x_1 - a / b * y_1;y_1 y_0;x_1 x_0;}else {x_1 1;y_1 0;}return d;
}
