정답은 맞췄는데 heap 메모리 터져버렸다. int 가 4byte라서 10억짜리 크기의 int 배열을 생성하게 되면, 40억바이트라 default heap size 에서는 터져버림. 실험해보니, 1억까지는 터지지 않는것을 발견. 아무튼 이렇게 풀면 안되고.....
여러가지 수식을 이용해서 풀어보려 했는데, 계속해서 한개씩 어긋나서 포기해버렸다. 구글에 검색해보니 유클리디안 호제법을 통해 gcd를 구하는 방법을 알아야 풀 수 있는 문제였다. 대학시절때 Number theory 수업에서 배웠는데.... 까먹어서 다시 설명 읽고 공부했다.
근데... 정답은 알겠다. gcd 구해서 N에서 나눈 몫을 구하면 답인데, 그게 왜 답이 되는지 도저히 이해 못 하겠다. 구글링을 아무리 해봐도 다들 저렇게만 구했다고만 써있고 왜 그래야하는지 안나와있네 ....힝힝
Data Scientist or Gourmet