Problem Info
I was working on the “Sum of Divisors” problem, and my solution gets the right answer most of the time, but gets the incorrect answer for larger numbers. Oddly, the incorrect answer is always the same number, 238111766.
My Work
#include <cmath>
#include <iostream>
using namespace std;
const long M = 1e9 + 7;
long seq_sum(long long a, long long b) { // Both inclusive
if (a > b) {
return 0;
}
return ((a + b) * (b - a + 1) / 2) % M; // (n)(n+1)/2
}
int main() {
long long total_sum = 0;
long n;
cin >> n;
const long up = (long) sqrt(n);
for (long i = 1; i <= up; i++) {
total_sum += i * (n / i);
total_sum %= M;
total_sum += seq_sum(up + 1, n / i);
total_sum %= M;
}
cout << total_sum << endl;
}
I’m looping through half the divisors: [1, sqrt(n)]
. For each divisor, I add it to the total based on the number of times the divisor appears ([n / i]
), while also adding the complementary divisors. To prevent double counting, I start summing the complementary divisors from [sqrt(n)] + 1
.
E.g. for the divisor 2
, I would add:
(2 * [n / 2]) + ([sqrt(n)]+1 + [sqrt(n)]+2 + ... + [n / 2])
.
What I’ve Tried
I suspect that I’m getting an integer overflow error, as my solution fails on large numbers. Therefore, I tried changing everything to long long
. I’m very new to C++, so I don’t know what else to try.
Question
I’m curious why my code returns a constant for the large cases, while it returns the correct answer for all other cases.