안 쓰던 블로그

약수 1: https://www.acmicpc.net/problem/4375 약수: https://www.acmicpc.net/problem/1037 C가 A의 약수라면, A/C도 A의 약수가 되어야 한다 C=3, A=24라면, 24/3=8도 24의 약수가 되어야 한다 그러면 중간을 기준으로 대칭을 이루게 된다 이 아이디어로 전체 약수를 구할 때 더 빠르게 구할 수 있다 전체 약수 구하기 1. 1~A로 모두 나눠보기: O(A)걸림. N개 수에 대해서 연산하므로 N*O(N) = O(N^2) 2. 1~루트(A)로 모두 나눠보기: O(루트(A))걸림. N개 수에 대해서 연산하면 N*O(루트(N))=O(N*루트(N)) 이런 아이디어는 범위가 클 때 사용 가능하다 N