목록디오판토스 방정식 (2)
블로그 옮겼습니다
Topcoder SRM 537 Div1(Easy) KingXNewCurrency
https://community.topcoder.com/stat?c=problem_statement&pm=11817 A, B, X
Algorithm/Problem Solving
2017. 8. 2. 16:38
UVa OJ 12775 - Gift Dilemma
https://uva.onlinejudge.org/external/127/12775.pdf \(0 = 200\)일 때,Ax + By + Cz = P 위의 디오판토스 방정식의 음이 아닌 정수 해 (x, y, z) 의 개수를 구하는 문제이다.우선 위에서 주어진 두 조건 중 두번째 조건을 주목하자. C / gcd(A, B, C) 가 200이상이라는 말은 일단적어도 입력으로 들어오는 C가 200이상이라는 것을 알 수 있다. 그러면 z를 고정시키고 그에 대한 (x, y) 를 구하는식으로 계산한다치면, 최악의 경우에도 고정하는 z의 개수는 10^8 / 200 이하, 즉 50만개 이하가 된다. 그럼 z를 고정시키고 x, y 를 구해보자. 만약 ..
Algorithm/Problem Solving
2017. 7. 23. 15:04