首页 > 代码库 > 双六---扩展欧几里得---挑战编程

双六---扩展欧几里得---挑战编程

2024-09-13 07:48:46   212人阅读

 

感谢http://www.cnblogs.com/oscar-cnblogs/p/6428920.html

题目描述 :
一个双六(类似大富翁的桌上游戏)上面有向前 向后无限延续的格子， 每个格子都写有整数。其中0号格子是起点，1号格子
是终点。而骰子上只有a,b,-a,-b四个整数，所以根据a和b的值的不同，有可能无法到达终点
掷出四个整数各多少次可以到达终点呢？如果解不唯一，输出任意一组即可。如果无解 输出-1

 

问题就是求 ax+by = c的通解

证明一: 一定存在 x, y 使得 ax+by = k*gcd(a, b) 

 设 a = gcd(a, b)*ra; b = gcd(a, b)*rb;

∵gcd(ra, rb) = 1

∴ax+by = (x*ra+y*rb)*gcd(a, b) = k*gcd(a, b) ----->k = (x*ra+y*rb)

有∵ gcd(ra, rb) = 1 由贝祖定理 一定存在 x, y  (x*ra+y*rb = gcd(ra, rb) = 1)

 

所以题目中的c = 1

1、那么一定要 a 和b互质 才能得到1

2、ax+by = 1是一个不定方程 

对于求其中的一组特解  可以使用 扩展欧几里得

extgcd(int a, int b, int &x, int &y)

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#define READ() freopen("in.txt", "r", stdin);
#define MAXV 2007
#define MAXE 20007
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
///扩展欧几里得

int extgcd(int a, int b, int &x, int &y)///c++的引用代入 也可以用指针
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int ans = extgcd(b, a%b, x, y);
    int tmp = x;
    x = y;
    y = tmp - a/b*y;
    return ans;
}
///更简洁的写法 书上的 直接将y传到x的位置 x传到y的位置然后y再-a/b*y
int Extgcd(int a, int b, int &x, int &y)
{
    int d = a;
    if (b != 0)
    {
        d = Extgcd(b, a%b, y, x);
        y -= a/b*x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}

int main()
{
    //READ()
    int a, b, x, y;
    int cnt[4] = {0};
    scanf("%d%d", &a, &b);
    if (extgcd(a, b, x, y) != 1)
    {
        cout << -1 << endl;
        return 0;
    }
    if (x > 0) cnt[0] = x;
    else if (x < 0) cnt[2] = -x;
    if (y > 0) cnt[1] = y;
    else if (y < 0) cnt[3] = -y;
    for (int i = 0; i < 4; i++) 
        cout << cnt[i];
    cout << endl;
    return 0;
}

 

双六---扩展欧几里得---挑战编程


联系
我们