글 읽기 - 선형디오판토스 방정식을 이용해 풀었습니다. 혹시 잘못 푼 것일까요?

ldg1291 5년 전 0

디오판토스 방정식을 이용해 풀었습니다만...

틀렸다고 나옵니다 혹시 어느 부분이 잘못되었는지 알 수 있을까요??

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

using namespace std;

long long a, b, c, d;

long long gcd(long long a, long long b) {
	

	while (a != 0 && b != 0) {
		long long M = max(a, b);
		long long m = min(a, b);

		a = M - m;
		b = m;
	}
	return a == 0 ? b : a;
}

long long lcm(long long a, long long b) {
	return a * b / gcd(a, b);
}

long long solve(long long a, long long b, long long c, long long d) {
	
	long long x = 1;
	while(a*x + c <= lcm(a, b)) {
		int tmp = a * x + c;
		if (tmp%b == d) {
			return tmp;
		}
		x++;
	}

	return -1;
}

int main()
{
	int N;

	scanf("%d", &N);

	while (N--) {
		scanf("%lld %lld %lld %lld", &a, &b, &c, &d);

		int g = gcd(a, b);

		if ((d - c) % g != 0) cout << -1 << endl;

		else {
			cout << solve(a, b, c, d) << endl;
		}
	}
}

chogahui05 5년 전 0

어떠한 부분이

선형 디오판토스 방정식인가요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

선형디오판토스 방정식을 이용해 풀었습니다. 혹시 잘못 푼 것일까요?

ldg1291 5년 전 0

chogahui05 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말