-1
세 개의 정렬 된 배열에서 A, B 및 C라고하면 A와 B 값의 범위는 < 10^5입니다. 반면에 C의 범위는 최대 10^10이지만 모든 C 요소는 완벽한 제곱입니다 .. A와 B의 모든 쌍을 계산하여 C의 어떤 요소와도 같도록합니다.하지만 그것을 시도했지만 복잡성은 o n^2) 그리고 나는 그것을 줄일 수 없다, 진행하는 방법에 대한 제안? A : 1, 3, 9, 14 B : [36, 49, 121] 대답 : 3 A 1에서 1, B 에서 49 마찬가지로 3 * 12 및 4 * 9제품이 o (n^2)보다 적은 수의 세 번째 아아 레이의 요소와 같음을 찾는
왜 O (n^2)에 대해 걱정합니까? 10^10 개의 C 요소가 있으므로 환경에서 처리 할 수 있습니다. A와 B의 모든 쌍은 단지 10^10이므로 A와 B는 10^5를 넘지 않습니다. C 값 자체를 계산하는 것보다 어렵지 않습니다. – Andrei
배열 A, B 및 C는 각각 10^5 개의 요소를 가질 수 있으므로 o (n^2)는 1 초 이내에 실행되지 않습니다. –
@Andrei @ 10 월 5 일과 10 일까지가는 원소의 값이라고 생각합니다^10, 요소의 수 없습니다. 적어도 샘플 입력에서 요소의 수는 4,3 및 3입니다. O (n^2)에 대한 걱정의 이유는 간단합니다. 문제는 더 빨라야합니다. 그 기초에 대한 성명서를 자세히 설명해 주시겠습니까? – Yunnosch