sqrt(a)*c/(b*d) = e*(f-g)/h - i를 만족하는 모든 갯수 찾기
숫자들의 범의는 n~m사이 n>=1, m<=16
m-n은 0~8사이
물론 반복문 a~i 모두 중첩시켜서 n~m까지 돌리면 타임리밋
a범위만 줄이면 될 거 같은데
아니 수업은 자료구조, 정렬, 트리 기초만 나가는데
시험엔 이런게 나오네 ㅋㅋㅋㅋ
이미 끝난 시험이긴 한데 풀어보고 싶긴 해서...
a=(~~)^2으로 수식 바꿔 생각해 봤는데 모르겠...
숫자들의 범의는 n~m사이 n>=1, m<=16
m-n은 0~8사이
물론 반복문 a~i 모두 중첩시켜서 n~m까지 돌리면 타임리밋
a범위만 줄이면 될 거 같은데
아니 수업은 자료구조, 정렬, 트리 기초만 나가는데
시험엔 이런게 나오네 ㅋㅋㅋㅋ
이미 끝난 시험이긴 한데 풀어보고 싶긴 해서...
a=(~~)^2으로 수식 바꿔 생각해 봤는데 모르겠...
조건이나 정확히 명시를 하든가
조건은 저게 다야 뭔 조건이 더 필요함? n,m입력받고 a~i 모두 n~m사이에 존재함 n,m입력값의 범위도 위에 썼고
예를들어 수식이 a = b / c 였고 n=2,m=6이면 2 = 4 / 2, 2 = 6 / 3, 3 = 6 / 2 이렇게 가능하고 총 가짓수인 3을 출력하는거
Meet in the middle
개수찾는데 MiM이 되나
좌변으로 가능한수 우변으로 가능한수 각각 대충 계산해도 10만개 이하잖음
좌변 가능한수 정렬하고 우변 가능한수 정렬하면 빠르게 셀수있다
a = 꼴로 정리하면 a = { (bde/c) * [ e(f-g)/h - i] }^2 임. 정수범위에서 이 식이 만족하려면 a가 정수 여야됌. 결국 bde 의 약수가 c여야 되고 즉 정수여야 되고 e(f-g)/h 값도 정수여야 a가 정수가 때문에 등식이 성립함
정수 아니여도 될걸
실수범위면 말이안되는게 값이 거의 무한대로 나올텐데 ㅋㅋㅋ
bde/c, e(f-g)/h-1가 다 정수일 이유가 없는데
값이라고 말하니깐 오해의 여지가 좀 생길듯. 답(경우의 수)를 말하는 거임 ㅎㅎ
그리고 bde/c에 e 잘못씀
만약 실수 범위면 1.1/1.1 , 1/1, 2.1/2.1 이런식으로 경우의 수는 무한대임. 문제가 이런식으로 주어지는건 말도 안되고 의미도 없음
e f g h 각각이 정수인거지 e(f-g)/h가 정수일 필요는 없다고
아 그러네 ㅋㅋㅋㅋ 우변 왼쪽 분자항 e 잘못썼네 ㅋㅋㅋ
아 그러네 e(f-g)/h항이 꼭 정수일 필요는 없을 듯. 앞에 항에 곱해지면서 변수가 생기니깐. 그러면 제곱 안에 항을 다 합쳐서 거기서 정수가 되는 경우의 수를 찾으면 되겠네 ㅎㅎ
여튼 요지는 우항의 분모들이 해당 항의 분자를 나눌 수 있게 구성되는 경우의 수를 찾으면 됨. 즉 약수를 찾으란 말임. 이렇게하면 좀 많이 좁혀질 거 같은데요
위에 오타있는데 ' 정수범위에서 이 식이 만족하려면 a가 정수 여야됌' 가 아니라 우항의 값이 정수여야 된다는 말임
위에서 약수의 경우의 수를 찾고 나머지 변수들이 가지는 경우의 수를 곱해주면 될 거같은데 나머지는 본인이 알아서 해보삼 ㅋㅋㅋ
ㄱㅅㄱㅅ 좀 해보다가 안되면 걍 메일 보내야겠음
브루트 포스해도 반복문 9^8번 정도 도는건데 이게 시간초과 남?
학교 oj라 교수님이 시간제한을 거심 브루트포스 쓰지 말라고
로컬에서 계산해놓고 답만 코드에 넣어서 출력하게 만들면 O(1)임 ㅅㄱ
우변이 0 이하가 될 수 없으므로 e*(f-g)/h > i 이고 f != g 여야할거 같은데
MITM에 관찰 몇개만 더하면 됨