[BOJ] 11661번 해의 개수

문제

방정식 Ax + By + C = 0의 해의 개수를 구하는 프로그램을 작성하시오.
A, B, C, x, y는 모두 정수이고, x1 ≤ x ≤ x2, y1 ≤ y ≤ y2인 해의 개수를 구해야 한다.

입력

첫째 줄에 A, B, C, x1, x2, y1, y2가 주어진다. 모든 정수는 -10⁸보다 크거나 같고, 10⁸보다 작거나 같은 정수이다.

출력

첫째 줄에 입력으로 주어진 방정식의 해의 개수를 출력한다.

예제

// 입력
1 1 1 -20 20 -30 30

// 출력
41

// 입력
20 30 40 50 60 70 80

// 출력
0

// 입력
-100 20 300 -100 200 -2000 3000

// 출력
301

// 입력
-10 8 4 -100 100 -200 300

// 출력
50

코드

• C++17

#include <iostream>
#include <cmath>
#include <tuple>
#include <algorithm>

using namespace std;

using ll = long long;

ll A, B, C, X1, X2, Y1, Y2;
ll ans;

// 확장된 유클리드 알고리즘
// { gcd(a, b), x, y }을 반환한다.
// 자세한 건 후술한다.
inline tuple<ll, ll, ll> extendedEuclidean(ll a, ll b)
{
    if (b == 0LL)
        return { a, 1LL, 0LL };
    ll g, x, y;
    tie(g, x, y) = extendedEuclidean(b, a % b);
    return { g, y, x - a / b * y };
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 해당 문제를 풀려면 먼저 디오판토스 방정식(http://bit.ly/2Z8C7co)에 대해서 알아야 한다.
    // 그 중 해당 문제는 선형 디오판토스 방정식(ax + by = c)을 풀으라는 것과 같다.
    // 선형 디오판토스 방정식이 해를 가지려면 c가 gcd(a, b)의 배수여야한다.
    // 해를 갖게 되면 베주 항등식(http://bit.ly/2XwOgb1)이라고 부른다.
    cin >> A >> B >> C >> X1 >> X2 >> Y1 >> Y2;

    // 베주 항등식인 ax + by = c에서
    // ax + by = gcd(a, b)일 때, 해를 구할 수 있는 알고리즘이 있다.
    // 그 알고리즘을 확장된 유클리드 알고리즘(http://bit.ly/2Z8eHE6)이라고 한다.
    // 이 문제는 해당 알고리즘을 이용하여, 해의 개수를 구해야 한다.
    ll g, x0, y0;
    tie(g, x0, y0) = extendedEuclidean(A, B);   

    // 이 문제는 Corner Case가 매우 많으므로 주의한다.
    if (X1 > X2 || Y1 > Y2)
        ans = 0;
    else if (A == 0 && B == 0)
    {
        if (C == 0)
            ans = (X2 - X1 + 1) * (Y2 - Y1 + 1);
    }
    else if (C % g != 0)
        ans = 0;
    else if (A == 0)
    {
        ll s = -C / B;
        if (Y1 <= s && s <= Y2)
            ans = X2 - X1 + 1;
    }
    else if (B == 0)
    {
        ll s = -C / A;
        if (X1 <= s && s <= X2)
            ans = Y2 - Y1 + 1;
    }
    else
    {
        // 또 다른 해 x1, y1이 있다면, ax0 + by0 = ax1 + by1일 것이다.
        // 정리하면 a(x1 - x0) = b(y0 - y1)이다.
        // 이 식이 성립하려면 (y0 - y1)가 a의 배수여야 한다.
        // (y0 - y1) = a / b * K(K는 정수)이고, 여기서 b는 gcd(a, b)의 배수이므로 다시 정리하면
        // (y0 - y1) = a / gcd(a, b) * K가 된다.
        // 따라서, y1 = y0 - a / gcd(a, b) * K이다.
        // 마찬가지로 x1 = x0 + b / gcd(a, b) * K가 된다.
        // 이를 확장해 주어진 범위에 대입하여 풀면 된다.
        x0 *= -C / g;
        y0 *= -C / g;   

        ll start1, start2, end1, end2;
        if (B / g < 0)
        {
            start1 = ceil(double(X2 - x0) / B * g);
            end1 = floor(double(X1 - x0) / B * g);
        }
        else
        {
            start1 = ceil(double(X1 - x0) / B * g);
            end1 = floor(double(X2 - x0) / B * g);
        }
        if (A / g < 0)
        {
            start2 = ceil(double(y0 - Y1) / A * g);
            end2 = floor(double(y0 - Y2) / A * g);
        }
        else
        {
            start2 = ceil(double(y0 - Y2) / A * g);
            end2 = floor(double(y0 - Y1) / A * g);
        }
        ans = max(min(end1, end2) - max(start1, start2) + 1, 0LL);
    }   
    cout << ans;
}

• C# 6.0

using System;

namespace AlgorithmsByCsharp
{

    class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split();
            long a = long.Parse(inputs[0]);
            long b = long.Parse(inputs[1]);
            long c = long.Parse(inputs[2]);
            long x1 = long.Parse(inputs[3]);
            long x2 = long.Parse(inputs[4]);
            long y1 = long.Parse(inputs[5]);
            long y2 = long.Parse(inputs[6]);

            var tuple = extendedEuclidean(a, b);
            long g = tuple.Item1, x0 = tuple.Item2, y0 = tuple.Item3;
            long ans = 0;

            if (x1 > x2 || y1 > y2)
                ans = 0;
            else if (a == 0 && b == 0)
            {
                if (c == 0)
                    ans = (x2 - x1 + 1) * (y2 - y1 + 1);
            }
            else if (c % g != 0)
                ans = 0;
            else if (a == 0)
            {
                long temp = -c / b;
                if (y1 <= temp && temp <= y2)
                    ans = (x2 - x1 + 1);
            }
            else if (b == 0)
            {
                long temp = -c / a;
                if (x1 <= temp && temp <= x2)
                    ans = (y2 - y1 + 1);
            }
            else
            {
                x0 *= -c / g;
                y0 *= -c / g;

                double start1, end1, start2, end2;
                if (b / g < 0)
                {
                    start1 = Math.Ceiling((double)(x2 - x0) / b * g);
                    end1 = Math.Floor((double)(x1 - x0) / b * g);
                }
                else
                {
                    start1 = Math.Ceiling((double)(x1 - x0) / b * g);
                    end1 = Math.Floor((double)(x2 - x0) / b * g);
                }
                if (a / g < 0)
                {
                    start2 = Math.Ceiling((double)(y0 - y1) / a * g);
                    end2 = Math.Floor((double)(y0 - y2) / a * g);
                }
                else
                {
                    start2 = Math.Ceiling((double)(y0 - y2) / a * g);
                    end2 = Math.Floor((double)(y0 - y1) / a * g);
                }
                double start = Math.Max(start1, start2);
                double end = Math.Min(end1, end2);
                ans = (long)Math.Max(end - start + 1, 0.0);
            }

            Console.Write(ans);
        }

        static Tuple<long, long, long> extendedEuclidean(long a, long b)
        {
            if (b == 0L)
                return Tuple.Create(a, 1L, 0L);
            var temp = extendedEuclidean(b, a % b);
            long g = temp.Item1, x = temp.Item2, y = temp.Item3;
            return Tuple.Create(g, y, x - a / b * y);
        }

    }
}

• Python 3

import sys
from math import ceil, floor

input = sys.stdin.readline
print = sys.stdout.write

def extendedEuclidean(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x, y = extendedEuclidean(b, a % b)
    return (g, y, x - a / b * y)

a, b, c, x1, x2, y1, y2 = map(int, input().split())
g, x0, y0 = extendedEuclidean(a, b)
ans = 0

if x1 > x2 or y1 > y2:
    ans = 0
elif a == 0 and b == 0:
    if c == 0:
        ans = (x2 - x1 + 1) * (y2 - y1 + 1)
elif c % g != 0:
    ans = 0
elif a == 0:
    t = -c // b
    if y1 < t < y2:
        ans = (x2 - x1 + 1)
elif b == 0:
    t = -c // a
    if x1 < t < x2:
        ans = (y2 - y1 + 1)
else:
    x0 *= -c // g
    y0 *= -c // g

    start1 = 0; end1 = 0; start2 = 0; end2 = 0
    if b / g < 0:
        start1 = ceil((x2 - x0) / b * g)
        end1 = floor((x1 - x0) / b * g)
    else:
        start1 = ceil((x1 - x0) / b * g)
        end1 = floor((x2 - x0) / b * g)
    if a / g < 0:
        start2 = ceil((y0 - y1) / a * g)
        end2 = floor((y0 - y2) / a * g)
    else:
        start2 = ceil((y0 - y2) / a * g)
        end2 = floor((y0 - y1) / a * g)
    end = min(end1, end2)
    start = max(start1, start2)
    ans = max(end - start + 1, 0)

print(str(ans))