求线性Diophantine方程的给定区间的解数和解数 [英] Finding the number of solutions and the solutions in a given interval of a Linear Diophantine Equation

问题描述

我最近研究了线性丢番图方程，并发现了一种使用扩展欧几里德法的可能解决方案，但是如果给定可允许的'x'和'范围，该怎么办?y'，并要求计算解决方案数量，并查找解决方案.我已经在此处中查看了此信息，但无法进一步理解清楚地.可以理解任何其他方法或以更简单的语言来解释上述方法.谢谢.

I recently studied Linear Diophantine Equation and found one possible solution using Extended Euclidean approach but what if we are given a range of permissible 'x' and 'y' and asked to count the number of solutions and also find the solutions. I already looked this at here but was not able to understand it more clearly. Any other approach or explaining the above approach in easier words is appreciated. Thanks.

推荐答案

我已阅读此问题来检查代码的正确性.这是我的代码的python版本:

I have read this in cp-algorithms. The code was unclear to me, but I have written a code, which works correctly and is easier to understand. Actually, I have checked the correctness of my code by solving this problem in codeforces. It is the python version of my code :

from math import ceil, gcd, floor


def GCD(a, b):
    if b == 0:
        x = 1
        y = 0
        return(x, y)
    A, B = GCD(b, a % b)
    x = B
    y = A-B*(a//b)
    return(x, y)


def find_ans(a, b, c, minx, maxx, miny, maxy):
    if c % gcd(abs(a), abs(b)) != 0:
        return 0
    sb = b//abs(b)  # sign of a
    sa = a//abs(a)  # sign of b
    x, y = GCD(abs(a), abs(b))  # a solution to the equation
    x *= sa  # adjusting the sign of x
    y *= sb  # adjusting the sign of x
    g = gcd(abs(a), abs(b))
    x *= c//g
    y *= c//g
    # lk1 (left_k) = lower bound for k due to [minx , maxx]
    lk1 = (minx-x)*g/b  # x+k*b/g >= minx --> k >= (minx-x)*g/b (if b>0)
    # rk1 (right_k) = upper bound for k due to [minx , maxx]
    rk1 = (maxx-x)*g/b  # x+k*b/g <= maxx --> k <= (maxx-x)*g/b (if b>0)
    # till this line of code, we have assumed that b>0 and we have : (minx-x)*g/b <= k <= (maxx-x)*g/b
    # if b<0, then : (minx-x)*g/b >= k >= (maxx-x)*g/b . Thus the lower bound and the upper bound will change
    if sb == -1:
        lk1, rk1 = rk1, lk1
    # for example if lk1= 1.5 , we have k>=2 ( the reason is that k must be integer), so we have to use ceil for lower bound
    lk1 = ceil(lk1)
    # for example if lk1= 10.5 , we have k<=10 , so we have to use floor for upper bound
    rk1 = floor(rk1)

    # we do the same thing for a
    rk2 = (y-miny)*g/a  # y-k*a/g >= miny --> k <= (y-miny)*g/a (if a>0)
    lk2 = (y-maxy)*g/a  # y-k*a/g <= maxy --> k >= lk2 = (y-maxy)*g/a (if a>0)
    if sa == -1:
        lk2, rk2 = rk2, lk2
    lk2 = ceil(lk2)
    rk2 = floor(rk2)
    #### finding the interval ####
    lans = max(lk1, lk2)  # lower bound of interval
    rans = min(rk1, rk2)  # upper bound of interval
    # it occurs when we have ( lk1 ------ rk1   lk2 ------ rk2 ) or (lk2 ------- rk2   lk1 -------- rk1).[lk1,rk1] and [lk2,rk2] don't have intersection
    if rans < lans:
        print(0)
    else:
        print(rans-lans+1)

这篇关于求线性Diophantine方程的给定区间的解数和解数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！