글 읽기 - 3955번 좀 도와주세요!!!!

toy3323 8년 전 0

확장 유클리드 알고리즘을 사용하여서 답을 구했는데 틀렸다고 나옵니다.....

음수가 나오는 경우를 생각해서 gcd가 항상 1인 경우기 때문에 양수가 나올 때 까지 더해주는 방식으로 해를 구하였는데

예제의 경우는 모두 맞게 나오고 다른 테스트 케이스에 대해서도 넣어봣는데 정상적으로 나오는 것 같습니다.

어느 부분이 틀린 것 일까요??

#include <cstdio>
int ext(int a, int b, int *x, int *y){
	if (a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = ext(b%a, a, &x1, &y1);
	*x = y1 - (b / a) * x1;
	*y = x1;
	return gcd;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int a, b,x,y;
		scanf("%d %d", &a, &b);
		ext(a, b, &x, &y);
		if (!x || !y)
			printf("IMPOSSIBLE\n");
		else {
			if (y < 0)
				while (y <= 0)
					y+= a;
			printf("%d\n",y);
		}
	}
	return 0;
}

dohoon 2년 전 0

10^9을 넘기면 안됩니다.

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

문제

문제

출처

ICPC

3955번 좀 도와주세요!!!!

toy3323 8년 전 0

dohoon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말