에너지 수확
시간 제한1초메모리 제한512 MB
1≤x≤n, 1≤y≤m인 모든 격자점 (x,y)에서 원점까지의 에너지 손실 2*gcd(x,y)-1의 합을 구한다.
문제
DongDong은 직사각형 모양의 땅을 가지고 있다. 이 땅에는 태양으로부터 에너지를 수확하는 특별한 에너지 식물을 심을 수 있다. 식물들이 에너지를 수확한 뒤, DongDong은 에너지 집결 기계를 사용해 식물들이 모은 태양 에너지를 한 곳으로 모으려 한다.
DongDong의 식물들은 n개의 행에 각각 m그루씩 가지런히 심어져 있다. 인접한 식물 사이의 세로 거리와 가로 거리는 모두 같다. 따라서 각 식물은 좌표 (x, y)로 나타낼 수 있으며, x는 1부터 n까지, y는 1부터 m까지의 값을 가진다. 이는 식물이 x번째 행의 y번째 열에 있다는 뜻이다.
에너지 집결 기계는 상당히 크고 옮기기 어려워서, DongDong은 좌표 (0, 0)에 있는 구석에 기계를 두었다. 에너지를 모으는 과정에서 일정량의 에너지가 손실될 수밖에 없다. 식물과 집결 기계를 잇는 선분이 k개의 다른 식물과 교차하면, 손실되는 에너지는 2k + 1 단위이다. 예를 들어 기계가 (2, 4)에 있는 식물의 에너지를 모으는데, (2, 1)에 있는 식물 하나가 두 지점 사이의 선분 위에 있으면 손실되는 에너지는 3이다. 참고: 선분 위에 다른 식물이 없으면 1 단위의 에너지가 손실된다. 이제 집결 과정에서 발생하는 총 에너지 손실을 구해야 한다.
다음은 n = 5, m = 4일 때의 에너지 집결 예시이다. 식물은 모두 20그루이다. 각 식물 옆에 적힌 숫자는 그 식물의 에너지 손실을 나타낸다.
이 예시에서 총 에너지 손실은 36이다.
입력
입력은 두 정수 n과 m을 포함하는 한 줄로 이루어진다.
출력
총 에너지 손실을 나타내는 정수 하나를 출력한다.
제한
1 ≤ n, m ≤ 100,000