Boj 17425) 약수의 합

문제

백준 17425

설명

cout 을 쓸 경우 fastio 설정을 처음에 안해놓으면 시간초과남.

처음에 값을 미리 구해놓지 않으면 시간초과남.

발상을 약수를 구한다 가 아니라 어떤 두 수는 서로 곱해서 나온 수의 약수다 라고 생각해야함.

• 그 발상으로 f 를 구하고 d 를 주어진 조건으로 만들면 됨.

약수의 합 2

약수의 합2 도 비슷하게 풀 수 있는데, 얘는 비슷한 발상을 O(n) 에 풀 수 있음.

long long ans = 0;
for (int i = 1; i <= n; i++)
	ans += (n / i)*i;

시간 복잡도

O(N*Log(N))

코드

#include <bits/stdc++.h>
using namespace std;

long long f[1000001];
long long g[1000001];

int main()
{
	cin.tie(0)->ios::sync_with_stdio(0); 
	cout.tie(0); setvbuf(stdout, nullptr, _IOFBF, BUFSIZ);
	
	const int MAX = 1000000;
	for (int j = 1; j <= MAX; j++)
		for (int i = 1; i*j <= MAX; i++)
			f[i*j] += i;
	for (int i = 1; i <= MAX; i++)
		g[i] = f[i] + g[i - 1];

	int t, n;
	cin >> t;
	while (t--)
	{
		cin >> n;
		cout << g[n] << '\n';
	}

}