[G4] 백준 17425번 약수의 합 C++ 누적 합

리뷰

 

https://www.acmicpc.net/problem/17425

약수의 합의 누적합을구하는 문제

 

 

전역 변수

• N : n의 최대값을 정의할 정수형 상수 변수
• t : 테스트 케이스의 개수를 저장할 변수
• n : g(N)을 구하기 위한 인덱스를 저장할 변수

 

함수

없음

 

 

문제풀이

1. 약수의 합을 저장할 long long타입의 벡터 F를 N크기로, 모든 값은 1인 상태로 초기화 한다.
2. 2부터 N - 1까지의 수를 순회하며 자신의 배수인 수에 자기 자신을 더해준다.
3. long long타입의 벡터 G를 N크기로 초기화 해준다.
4. 1부터 N - 1까지의 수를 순회하며 벡터 G에 누적합을 저장해 준다.
5. t를 입력 받고, t번의 while루프를 순회해 준다.
6. 매 루프타마다 n에 값을 입력 받고, G의 n번 인덱스 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 알고리즘 분류에 에라토스테네스의 체가 있는 걸 보니 소수를 통한 최적화가 가능한 문제인 듯 싶다.
• int타입을 사용 시 오버플로우가 나타날 것 같아 long long타입을 사용해 주었다.

 

정답 코드

#include<iostream>
#include<vector>
#define ll long long
using namespace std;

const int N = 1000001;
int t, n;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	vector<ll> F(N, 1);
	for (int i = 2; i < N; ++i)
		for (int j = i; j < N; j += i)
			F[j] += i;

	vector<ll> G(N);
	for (int i = 1; i < N; ++i) G[i] = G[i - 1] + F[i];

	cin >> t;
	while (t--) {
		cin >> n;
		cout << G[n] << "\n";
	}
}