문제 정리
F(n)은 약수의 합이다. a부터 b까지 모든 F(n)의 합을 구하는 문제
생각해야 할 점
a와 b가 모두 10^12범위이다. O(n)으로 해도 터져버림
첫 번째 시도
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;
int main() {
i64 a, b;
scanf("%lld %lld", &a, &b);
i64 sum = 0;
for (i64 k = 1; k * k <= 1000000000000; k++) {
if (n % k == 0) {
sum += k;
if (k == 1000000000000/k)
sum += n/k;
}
}
printf("%lld", sum);
return 0;
}이렇게 하면 되지 않을까 싶었지만 이러면 하나의 수 밖에 구하지 못한다. a부터 b의 범위가 10^6이기 때문에 10^6 * 10^6이 되어서 10^12가 되어 버린다. 터져버림
두 번째 시도
숫자 하나 당 약수를 구하는 게 시간이 많이 걸리므로 반대로 생각해보자.
숫자 중 2를 약수로 가지고 있는 수라면 이 수는 2의 배수이다.
그래서 1부터 차근히 배수를 더해나가보자
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;
int main() {
i64 a, b;
scanf("%lld %lld", &a, &b);
i64 sum = 0;
for (int k = 1; k <= 1000000; k++) {
for (i64 j = ((a + k - 1) / k) * k ; j <= b; j += k) {
sum += k;
if (j / k > 1000000)
sum += j / k;
}
}
cout << sum << endl;
return 0;
}
일단 반복문 내부부터 보자
for (int k = 1; k <= 1000000; k++) {
for (i64 j = ((a + k - 1) / k) * k ; j <= b; j += k) {
sum += k;
}
}1의 배수부터 10^6의 배수까지 확인한다.
a부터 b 사이의 모든 배수를 확인하면 된다. 여기서 시작점인 a가 k의 배수가 아닐 수 있으므로 ((a + k - 1) / k) * k부터 시작한다.
(a + k - 1) / k가 올림을 나타낸다. k가 3일 때 a가 1이면 1, a가 2이면 1, a가 3이면 1, a가 4이면 2 ... 숫자를 올림한 다음 k를 곱하면 a보다 큰 배수를 구할 수 있다. 이후 k를 더해가면서 배수의 합을 구한다.
아니 그러면 10^6보다 큰 수들은 어떻게 구해야 할까.
a * b = c (a < b)라고 해보자. 만약 a가 10^6보다 크다면? 구하는 수의 범위가 10^12라서 a는 10^6보다 커질 수 없다.
그럼 b가 10^6보다 크다면? 이건 가능성이 있다. 그런데 b가 존재한다면 10^6보다 작은 a도 존재해야 할거고 그럼 이전에 구했던 a로 b도 구할 수 있다!
for (int k = 1; k <= 1000000; k++) {
for (i64 j = ((a + k - 1) / k) * k ; j <= b; j += k) {
sum += k;
if (j / k > 1000000)
sum += j / k;
}
}
그래서 이렇게 구할 수 있다~~
처음에 들었을 때 이게 뭐지??? 어떻게 돌아간다고??? 싶었는데 다시 확인해보니 알겠다. 헝 빠릿한 두뇌를 가지고 싶음