아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

넓이가 홀수인 격자 정사각형

시간 제한5초메모리 제한256 MB

요약
각 m과 n 격자 안에 들어가고 넓이가 홀수인 격자 정사각형 개수를 셉니다.
난이도

보통10점 중 7점

유형
조합론, 수학, 기하
정답자
아직 제출이 없습니다

문제

격자 정사각형은 네 꼭짓점이 모두 격자점 위에 있는 정사각형이다. 격자점은 xx좌표와 yy좌표가 모두 정수인 점이다. 예를 들어 (1,5)(1, 5)는 격자점이지만 (1,1.5)(1, 1.5)는 격자점이 아니다.

m×nm \times n 격자는 가로로 mm칸, 세로로 nn칸인 격자다. 이 격자의 격자점은 0≤x≤m0 \le x \le m, 0≤y≤n0 \le y \le n을 만족하는 정수 점 (x,y)(x, y) 전체다.

격자 안에 들어가는 격자 정사각형에는 변이 축에 평행한 것도 있고 기울어진 것도 있다. 한 변에 대응하는 벡터가 (p,q)(p, q)인 격자 정사각형의 넓이는 p2+q2p^2 + q^2이므로, 기울어진 정사각형도 넓이가 항상 정수다. 벡터가 (1,2)(1, 2)인 정사각형은 넓이가 55로 홀수이고, (1,1)(1, 1)인 정사각형은 넓이가 22로 짝수다.

격자의 크기가 주어졌을 때, 격자 안에 들어가고 넓이가 홀수인 격자 정사각형의 개수를 구하는 프로그램을 작성하시오.

두 격자 정사각형이 네 변을 모두 공유하지 않으면 서로 다른 정사각형이다.

입력

입력은 최대 50000줄이다. 각 줄에는 격자의 크기를 나타내는 두 정수 mm과 nn이 주어진다. (1≤m,n≤1000001 \le m, n \le 100000)

마지막 줄에는 00이 두 개 주어진다. 이 줄은 처리하지 않는다.

출력

주어진 격자마다 넓이가 홀수인 격자 정사각형의 개수를 한 줄에 하나씩 출력한다. 정답은 항상 64비트 부호 있는 정수 범위 안이다.

예제1

  1. 예제 1

    입력
    2 2
    3 3
    4 4
    0 0
    
    예상 출력
    4
    12
    28