백준15888 정답은 이수근이야!!

작성일 | In

문제 링크

  • http://icpc.me/15888

문제 출처

    • 제2회 천하제일 코딩대회 예선 D번

사용 알고리즘

  • 근의 공식

시간복잡도

  • 상수 시간

풀이

이수근인지 판별하기 위하여 2^k꼴의 숫자를 미리 구해놓읍시다.

방정식은 ax2 + bx + c = 0 꼴로 구성이 되고, 이 식은 x2 + (b/a)x + (c/a) = 0과 동치입니다.
방정식이 정수해를 갖기 위해서는 (b/a)와 (c/a) 모두 정수여야 합니다. 그러므로 b%a != 0 이거나 c%a != 0 이면 둘다틀렸근 을 출력해줍니다.
판별식이 0 이하인 경우에도 둘다틀렸근 을 출력해줍니다.

위에서 언급한 경우를 제외하면 가능한 경우는 이수근 혹은 정수근 뿐입니다.
근과 계수의 관계와 미리 구해놓은 2^k꼴의 수를 이용해 이수근 인지 판별해봅시다.
2^k꼴인 두 수 x, y에 대해 합이 -(b/a)이고, 곱이 (c/a)인 경우가 있다면 이수근 입니다.
반대의 경우에는 정수근 입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

int bin[8] = {2, 4, 8, 16, 32, 64, 128, 256};
double a, b, c;

int main(){
	scanf("%lf %lf %lf", &a, &b, &c);

	if((int)b % (int)a){
		printf("둘다틀렸근");
		return 0;
	}
	if((int)c % (int)a){
		printf("둘다틀렸근");
		return 0;
	}

	b /= a; c /= a; a /= a;

	if(b*b - 4*a*c <= 0){
		printf("둘다틀렸근");
		return 0;
	}

	for(int i=0; i<8; i++){
		for(int j=0; j<8; j++){
			if(i==j) continue;
			if(bin[i] + bin[j] == -b && bin[i] * bin[j] == c){
				printf("이수근");
				return 0;
			}
		}
	}

	for(int i=-200; i<=200; i++){
		for(int j=-200; j<=200; j++){
			if(i+j == -b && i*j == c){
				printf("정수근");
				return 0;
			}
		}
	}

	printf("둘다틀렸근");
}