[Number Theory]디오판토스 일차방정식의 해의 존재성 증명

오늘도 코드포스 문제풀이를 하던 도중, 익숙한 방정식의 형태가 등장했는데, 정확히 어떻게 풀어야 하는지 기억이 잘 나지 않아, 이번 기회에 확실하게 정리하려고 한다.

Div.2 # 955 D번을 풀던 중, 다음과 같은 방정식을 마주하게 되었다.

$$ D = px + qy + rz + ... (x, y,z,... \in \mathbb{Z}) $$

다음과 같은 형태의 방정식을 "디오판토스 일차방정식" 이라고 한다.
실제로 디오판토스 방정식은 차수가 하나씩 늘어갈수록 난이도가 지수적으로 증가한다고 한다.
지나치게 깊게 들어가지 않으면서, 적절하게 해당 해의 존재성을 증명하는 방법을 알아보자.

위 방정식의 해가 존재하는 지를 구성적 증명으로 처리하려면, 완전 탐색 or 그래프 탐색 방식으로 접근해야 하는데, 이는 지나치게 많은 경우의 수에 의해 매우 비효율적인 알고리즘이 탄생하게 된다.

우리가 문제에서 정확히 구해야 하는 것은 "해의 존재성" 이고, 이것만을 빠르게 뽑아내기 위한 알고리즘이 우리가 하고자 하는 구현이므로, 위와 같은 방정식을 빠르게 풀기 위한 "베주 항등식" 을 이용한 증명을 알아보자.

베주 항등식

정의

• 적어도 하나는 0이 아닌 두 정수 a와 b에 대해, 적절한 정수 x, y가 존재하여, 다음 등식을 만족한다.

$$ ax +by=gcd(a,b) $$

• $gcd(a,b)$는 정수 x,y 에 대하여, $ax+by$ 형태로 표현할 수 있는 가장 작은 자연수이다.
• 정수 $x, y$에 대하여 $ax+by$형태로 표현되는 모든 정수는 $gcd(a,b)$의 배수이다.

책임

• 두 정수의 최대공약수가 “항상” 그 두 수의 정수 배의 합으로 표현될 수 있음
• 또한 역과 이도 모두 성립하기에, 두 수의 정수배의 합은 두 수의 최대공약수의 정수배와 같음도 의미
• 이는 2개 이상의 적어도 하나는 0이 아닌 정수들에 관해서도 성립한다
  • 만약 새로운 항을 갖는 c 가 있을경우, 해당 c는 0이 계수로 붙은 $ax + by$ 로 볼 수 있기 때문 

증명

• 위키 참조: https://ko.wikipedia.org/wiki/베주_항등식

베주 항등식 - 위키백과, 우리 모두의 백과사전

 

현재 문제에 응용

현재 항의 갯수는 $(n-k)(m-k)$개가 존재한다.

$$ D = px + qy + rz + ... (x, y,z,... \in \mathbb{Z}) $$

따라서, 가능한 모든 선택지에 대하여, 모든 x, y, z, … 의 최대 공약수를 구한 뒤, 해당 gcd(x, y, z, …) 에 대하여 $D\,mod\, gcd(x,y,z,...) = 0$인지 검사하면 된다.

단, 베주 항등식의 정의에 따라

• $D = 0$ 이거나,
• 모든 $x, y, z, … = 0$ 인 경우를 제외하고 계산해야 한다.

소스코드

#include <bits/stdc++.h>
#define ll long long
#define INF ((int)1e9 + 10)
#define lINF ((ll)1e18 + 10LL)
const ll MOD = 1000000007LL;
// #include <atcoder/modint.hpp>
// using mint = atcoder::modint998244353;

using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

void Solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<ll>> arr(n, vector<ll>(m, 0));
    ll capsSum = 0, noCapsSum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            noCapsSum += arr[i][j];
        }
    }
    vector<vector<ll>> caps(n, vector<ll>(m, 0));
    for (int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < m; j++) {
            if (temp[j] == '1') {
                caps[i][j] = 1;
                capsSum += arr[i][j];
            }
        }
    }
    noCapsSum -= capsSum;
    vector<vector<ll>> psum(n + 1, vector<ll>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            psum[i][j] = caps[i - 1][j - 1];
            psum[i][j] += psum[i][j - 1];
            psum[i][j] += psum[i - 1][j];
            psum[i][j] -= psum[i - 1][j - 1];
        }
    }

    set<ll> can;

    for (int i = k; i <= n; i++) {
        for (int j = k; j <= m; j++) {
            ll change = (psum[i][j] - psum[i - k][j] - psum[i][j - k] +
                         psum[i - k][j - k]);
            if (k * k - 2 * change != 0) can.insert(abs(k * k - 2 * change));
        }
    }
    ll diff = abs(capsSum - noCapsSum);
    ll val = 0;
    for (auto &&i : can) {
        if (i == 0) {
            continue;
        }
        val = gcd(val, i);
    }
    if (capsSum == noCapsSum) {
        cout << "YES\n";
        return;
    }
    if (val > 0 && diff % val == 0) {
        cout << "YES\n";
        return;
    }

    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) Solve();
    return 0;
}

/*
찾아야 할 것들
1. int 오버플로우, out of bounds
2. 특수한 경우(n=1?)
3. 잘못된 가정 & 증명

*아무것도 하지 않는 대신 무언가를 수행하기. 체계적인 상태를 유지.
*적어두기 & 구하고자 하는 것의 계층 구조 표현 -> 정확히 & 입체적으로 파악
*한가지 접근 방식에 얽메이지 말기 -> 응용의 끝 알기
*/
// 알고리즘의 작동방식 "완전히" 이해하려 노력하기
// 수행 목표
// 1. 아이디어 획득 : "추론"
//     - 문제 알고리즘/특징의 "증명"으로 아이디어
//         - {BruteForce, greedy, D&C, DP, graph, math}
//     - 전체 알고리즘이 “결국 구하고자 하는 것” 놓치지 않기
//     - “책임” 뽑아내기
//         - 각 기능들이 어떤 책임을 가지고 있는지
//         - “어떤 패턴”으로 동작하는지
//     - 가장 Naive한 상태/알고리즘부터 시작하기 (완전 탐색, 단순 자료구조)
//     - 뚜렷한 증명이 나오지 않을 땐, 어떤 기준을 만들고 나눠서 보기
//     - 뚜렷한 최적화 기법이 떠오르지 않을 땐, 문제에 주어진 특이한 특징을 잡기
//     - 단위 동작의 조건 분기 파악
//     - 가장 극단적인 경우에서 추론 (가장 차이가 뚜렷한 예제)
// 2. "처음"부터 직접 경우의 수 전개(수식&도식화, 엄밀한 조건 정리)
//     - 알고리즘 내에 어떤 역할들이 있는지 -> 직접 들어가보기
//     - 알고리즘 내에 어떤 기능들이 있는지 -> 직접 수행해보기
//     - "끝까지 구체화"로 접근해야, "깔끔한 추상화"가 나온다.
// 3. cutting | 구현(차근차근 단순화 & 최적화)

/*
수학적 접근 방법
1. 불변성
2. 극단성
3. 홀짝성
4. 단조성
5. 선형성
6. 영역성
*/

/*
정당성 증명 방법
1. 귀납법 -> 결과값 만드는 점화식의 존재성을 증명하는 것
2. 귀류법 -> 결과값의 참/거짓을 가정하고 이전단계의 모순을 발견하여 증명
3. 경우에 의한 증명 -> 반례 찾기
4. 구성적 증명 -> 부분문제의 결과값을 만드는 원인를 분석하여 증명하는 방법
5. 비둘기집의 원리
6. 대각선 논법(연역법) -> A<C 이고 C<B 임을 이용해 A<B를 증명하는 방법
*/

/*
take notes.
// 다시 보는용이 아닌
// 현재의 흐름을 가장 잘 이어갈 수 있도록 !!!

2차원 누적합을 이용한 스위핑?
경우의 수?
*/

// commit 시 피드백할 것 Message로 남겨두기!!
// 틀리면 느낌표 추가하기