[usaco] 1.4 Arithmetic Progressions - usaco
2009.08.08 22:51 Edit
등차수열이 있을 때 n항까지 등차수열의 값이 어떤 두 수의 제곱의 합으로 나타내어지는 숫자들을 모두 출력하는 문제이다.
이것도 그냥 막 돌리다가는 제한시간에 걸리기 때문에 조금 생각 해야한다.
일단 250*250*2=125000이기 때문에 125000까지는 배열을 만들어서 해당하는 숫자가 두 수의 제곱의 합으로 나타내어지는가 하는것에 대한 판별 테이블을 만들고
시도 할 때는 두 수의 차이*(n-2)가 2*m*m보다 작다는 점을 알아내야한다.
이것도 그냥 막 돌리다가는 제한시간에 걸리기 때문에 조금 생각 해야한다.
일단 250*250*2=125000이기 때문에 125000까지는 배열을 만들어서 해당하는 숫자가 두 수의 제곱의 합으로 나타내어지는가 하는것에 대한 판별 테이블을 만들고
시도 할 때는 두 수의 차이*(n-2)가 2*m*m보다 작다는 점을 알아내야한다.
