알고리즘 관점에서 약수 문제 접근 방법 (C++)

약수

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<=1,000,000이면 N^2은 1조

1억을 1조라고 가정하면 10,000초 정도 걸린다. 2~3시간 정도

하지만 100만*루트100만=100만*1000=10억=약 10초

 

4375 1 문제 코드: https://github.com/proqk/Algorithm/blob/master/math/4375%201.cpp

1037 약수 문제 코드: https://github.com/proqk/Algorithm/blob/master/math/1037%20%EC%95%BD%EC%88%98.cpp

GitHub - proqk/Algorithm: BOJ problem solving https://www.acmicpc.net/user/proqk & https://foxtrotin.tistory.com/

---

근데 이렇게도 크다면, 두 가지 방법이 또 있다

약수 그 자체를 구해야 한다면 에라스토테네스의 체 같은 느낌으로 배수를 사용하여 구한다

약수의 개수를 구해야 한다면 아래같은 아이디어를 사용한다

약수의 합2: https://www.acmicpc.net/problem/17427

코드플러스 인강 캡쳐

N이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 N/1 내림 개 (3.5면 3)

N이하의 자연수 중에서 2을 약수로 갖는 수의 개수는 N/2 내림 개 

N이하의 자연수 중에서 3을 약수로 갖는 수의 개수는 N/3 내림 개

...

 

예)

7/1 = 7. 7이하의 자연수 중 1의 등장 횟수 7번

7/2 = 3. 7이하의 자연수 중 2의 등장 횟수 3번

..

여기에 원래 수까지 곱하면, 전체 합을 구할 수 있다

7/1 = 7 * 1 = 7

7/2 = 3 * 2 = 6 (2는 총 3번 나오고 더하면 6)

...

 

아래는 약수의 합2 코드

https://github.com/proqk/Algorithm/blob/master/math/17427%20%EC%95%BD%EC%88%98%EC%9D%98%20%ED%95%A92.cpp

GitHub - proqk/Algorithm: BOJ problem solving https://www.acmicpc.net/user/proqk & https://foxtrotin.tistory.com/

---

그런데 이렇게도 시간이 걸리는 문제가 있다

약수의 합: https://www.acmicpc.net/problem/17425

N이 주어졌을 때 N 이하 수들의 약수들의 전체 합 g(N)구하기

g(N)을 위의 방법으로 계산하면 O(N)이고,

테스트 케이스의 개수가 T라고 하면, O(TN)이다

T는 10만 * N은 100만 = 1000억 = 1000초 하지만 시간제한은 1초

 

에라스토테네스의 체에서 소수를 구할 때와 비슷하게,

배수 값을 갱신하는 배열을 사용하는 개념을 응용한다

vector<long long> d(n+1, 1);
for(int i=2;i<=n;i++){
	for(int j=1;i<=j;j++){
    	if(i%j==0) d[i]+=j;
    }
}

1번 아이디어)

24의 약수라 하면 N이 몇 이든 24의 약수는 24의 약수이다

그럼 24까지만 구하면 되겠다

 

2번 아이디어)

합배열 g를 두고, 1을 전부 채운다 (1은 모든 수의 약수니까)

i=2이면, 2의 배수 배열칸에 가서 +=2 를 한다

3의 배수에 +=3을 한다

..

그러면 위의 코드가 아래처럼 바뀐다

vector<long long> d(n+1, 1);
for(int i=2;i<=n;i++){
	for(int j=1;i*j<=n;j++){
    	d[i*j]+=i;
    }
}

위의 코드는 for 2번 돌면서 N개에 대해 N번 도니까 O(N^2)이다.

아래 코드는 항상 그런 것은 아니다.

n=7이라면 i=2일 때는 3번, 3일 때는 2번밖에 돌지 않는다. 

 

i=2일 때, j=1~N/2번

i=3일 때, j=1~N/3번

... 만큼 도니까

N/2 + N/3 +... N/N까지 하면 이 값은 log(N)

이것을 N번 하니까, Nlog(N) 이다.

---

17425 약수의 합 문제에서는, 각 자연수에 대한 약수의 합을 구하고,

또 1~x까지의 모든 수의 약수의 합의 총합을 구해야 했다.

 

각 자연수에 대한 약수의 합은 위의 코드로 해결했는데, 1~x까지의 수의 약수의 합의 총합을 구하기 위해서는 또 다른 계산이 필요하다

vector<long long> d(MAX+1, 1); //d[i] = i의 모든 약수 총합. 계산 완료
vector<long long> s(last +1); //1~x까지 자연수들의 "약수의 총합"의 총합
for (int i = 1;i <= last;i++) {
	s[i] = s[i - 1] + d[i];
}

d배열이 구해져 있는 상태라고 하면

s배열은 단지 이전 인덱스의 값+이번 d배열 값을 더하면 된다

그러면 1~x까지의 합을 담은 새로운 벡터 배열 s를 구할 수 있다

 

아래는 17425 약수의 합 문제 코드

https://github.com/proqk/Algorithm/blob/master/math/17425%20%EC%95%BD%EC%88%98%EC%9D%98%20%ED%95%A9.cpp

GitHub - proqk/Algorithm: BOJ problem solving https://www.acmicpc.net/user/proqk & https://foxtrotin.tistory.com/