3개의 댓글이 있습니다.

• 
  Taeyoon_Lee

  1~N사이 두 자연수의 GCD는 항상 1~N사이 자연수가 됩니다. 이것을 힌트로 삼아서 아래 질문들에 대한 결과값을 미리 계산합니다.

  1 GCD {1, 2, ... , N-1, N} => 1이 A개, 2가 B개, ... , N-1이 C개, N이 D개 나옴.
  2 GCD {1, 2, ... , N-1, N} => 1이 A개, 2가 B개....
  .
  .
  N-1 GCD ...
  N GCD ...

  예를 들어 N=3이라고 하면
  1 GCD {1, 2, 3} => 1이 3개
  2 GCD {1, 2, 3} => 1이 2개, 2가 1개
  3 GCD {1, 2, 3} => 1이 2개, 3이 1개

  M이 2라고 하면, 바로 위 결과값으로 답을 계산할 수 있습니다.
  총 1이 7개, 2가 1개, 3이 1개 남으니까요.

  M이 3이라고 하면,
  M이 2일 때까지 1이 7개 남았고, "1 GCD {1, 2, 3} => 1이 3개"니까, 7 x 3 = 21개의 1이 생길 거라고 계산할 수 있습니다.
  M이 2일 때까지 2는 1개 남았고, "2 GCD {1, 2, 3} => 1이 2개, 2가 1개"니까, 1이 2개 2가 1개 생길 테고요.
  M이 2일 때까지 3은 1개 남았고, "3 GCD {1, 2, 3} => 1이 2개, 3이 1개"니까, 1이 2개 3은 1개 생길 겁니다..
  전체적으로 1은 25개, 2는 1개, 3은 1개가 남겠네요..

  이런 식으로 쭉 계산을 해나가시면, O(N^2 + NM) 정도로 풀 수 있습니다. N과 M이 훨씬 크더라도 아주 빠르게 답을 찾는 어려운(?) 알고리즘이 존재하는데, 출제자의 의도는 아닌 것으로 보입니다.

  
  10년 전 link

• 
  jereneal20

  음.. 어떤 방법을 의도했는지는 파악했지만 복잡도가 O(N^2+NM)인지는 잘 모르겠네요..
  "M이 2일 때까지 3은 1개 남았고, "3 GCD {1, 2, 3} => 1이 2개, 3이 1개"니까, 1이 2개 3은 1개 생길 겁니다.." 라는 절차에서 계산하는데 N시간이 걸리니까 결과적으로 O(N^2+N^2M)이 될거같다는 생각이 들어서요..

  
  10년 전 link

• 
  Taeyoon_Lee

  N^2M이 될 것 같지만 실제로 해보면 그렇지가 않습니다. 왜냐하면, 어떤 수 K가 {1, 2, ..., N-1, N}과 하나씩 GCD계산을 해보면 결과값은 전부 K의 약수가 되고, 약수의 종류의 수는 사실 몇 개 안 되거든요. 이 부분의 저장 방식을 스마트하게(?) 구현하면 N^2M이 아닌 NM*상수 정도로 풀 수 있습니다.

  
  10년 전 link

• 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.