[C/C++] 선형방정식의 정수해 구하기 (1)

# Visual Studio 2019

# 가장 간단한 정수해를 구하는 프로그램

 

 

# 선형방정식 : 미지수의 최고차항의 차수가 1을 넘지 않는 다항 방정식. 변수는 하나일 수도, 둘 이상일 수도 있다.

본문에서는 미지수가 2개(x, y)인 선형방정식을 다루고자 하며, 모두 다음과 같은 꼴로 표현된다.

 

ax + by = c

 

이 식은 미지수가 2개이기 때문에, 한 쌍의 근을 구하려면 2개의 식이 필요하다. (연립방정식)

따라서, 이 부정방정식에서 알아낼 수 있는 것은 해들의 일반화 식이다.

부정방정식의 풀이는 해의 형태를 제시하는 게 일반적이다. 정수론에서는 무수한 해 중에서도 '정수해'만을 취급하기로 한다. 

 

 

# 부정방정식 : 식의 개수보다 미지수의 개수가 많아, 근이 무수히 많은 방정식

예를 들어, 부정방정식 x+y=10 의 해를 구한다고 생각해보자,

순서쌍으로 나타내면 ... (-2,12) (-1,11) (0,10) (1,9) (2,8) ... 로 무수히 많다는 것을 알 수 있다.

('자연수해'로 범위를 축소한다면 유한개의 해를 가질 수 있다)

 

 

# 선형방정식의 가장 간단한 정수해 구하기

하나의 정수해를 구하면, 일반화 식을 만들어 낼 수 있다. 선형방정식에서 간단한 정수해를 구하는 프로그램을 작성했다.

여기서 '간단한'은 두 해의 절댓값의 합이 가장 작은 것을 의미한다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {

	int a, b, result;
	int cnt1 = 0, cnt2;

	printf("Input A, B, result (Ax + By = result) (A < B) \n");
	scanf("%d %d %d", &a, &b, &result);

	for (int i = a;i < 100000; i += a) {
		cnt1 += 1; cnt2 = 1;
		for (int j = b;j > -100000;j -= b) {
			if (i + j == result) {
				printf("%d * %d + %d * %d = %d \n", a, cnt1, b, cnt2, i + j);
				exit();
			}
			cnt2 -= 1;
		}
	}

	getchar();
	return 0;
}

 

단순히 for문을 돌려 간단한 정수해를 찾아내는 프로그램이다.

유의할 점이 있다면 입력 형태에서 A<B 를 맞춰줘야 한다는 점이다. 비교해서 바꾸는 코드를 추가한다면 더 완벽한 프로그램

 

 

# 프로그램 이용 예시

 

(1) 7x + 17y = 60  을 풀고자 한다 (Ctrl + F5)

     Input A, B, result (Ax + By = result) (A < B)
     7 17 60

    7 * 11 + 17 * -1 = 60

 

(2) 11x + 4y = 21 을 풀고자 한다. 입력 조건이 A<B 이므로 4를 먼저 입력하고 11을 입력해준다.

 => 4x + 11y = 21 을 풀게 되는 것

      Input A, B, result (Ax + By = result) (A < B)
      4 11 34
      4 * 14 + 11 * -2 = 34

 

(3) 103x + 1001y = 1 을 풀고자 한다. 큰 숫자이다.

      이 방정식은 무리없이 계산되지만, 만약 값이 안나온다면 for 문 안의 '100000 / -100000' 를 조정하면 된다.

      Input A, B, result (Ax + By = result) (A < B)
      103 1001 1
     103 * 311 + 1001 * -32 = 1 

 

(5) 2x + 4y = 5 를 풀고자 한다 (Ctrl + F5)

      Input A, B, result (Ax + By = result) (A < B)
      2 4 5

     결과가 나오지 않는다.

     숫자가 크지도 않고, A<B 의 조건에도 위배되지 않았는데 왜일까?

     그 이유는 바로 정수해가 존재하지 않기 때문이다.