除数和取模求和问题：n达1e12时C++代码计算错误求助

定义函数S(i)为数字i的所有除数之和，例如S(18)=1+2+3+6+9+18=39。需计算1到n的S(i)%MOD的总和，其中n最大可达10^12。

采用的思路是：利用除数出现次数公式q=floor(n/i)，通过floor(n/q)确定相同出现次数的最后一个i，再用等差数列求和公式计算该区间除数和并乘以q累加。但当n极大时代码返回错误结果，无法通过测试，附上相关C++代码：

#include <iostream>
#include <cmath>

using namespace std;

const int MOD = 1000000007;

int main() {
    long long n;
    cin >> n;

    long long ans = 0;
    long long q = 0;
 
    long long a = 0;
    long long s = 0;
    long long ultimo_i = 0;

   for (long long i=1;i<=n;) {
        q = static_cast<long long>(floor(n / i));
        ultimo_i = static_cast<long long>(floor(n) / q);
        a = (ultimo_i - i + 1);
        s = ((i+ultimo_i) * a) / 2;
        ans += (s * q);
        i += a;
    }
    
    ans %= MOD;

    cout << ans << endl;

    return 0;
}

代码存在三个核心问题，导致大数计算出错：

• 浮点数精度丢失：调用floor(n/i)时，n是1e12级别的整数，转成double会丢失精度，导致计算出的q或ultimo_i错误。C++中整数除法n/i本身就是向下取整，完全不需要floor。
• 整数溢出：当n=1e12时，(i+ultimo_i)*a的结果可能接近2e18，后续乘以q（最多1e12）会直接溢出，导致ans变成负数或错误值。
• 模运算时机错误：仅在最后对ans取模，累加过程中ans早已溢出，失去正确性。

修正后的代码：

#include <iostream>
using namespace std;

const int MOD = 1000000007;
const long long INV2 = 500000004; // 2在MOD下的逆元，因MOD是质数，逆元为(MOD+1)/2

int main() {
    long long n;
    cin >> n;

    long long ans = 0;
    for (long long i = 1; i <= n;) {
        long long q = n / i;
        long long ultimo_i = n / q;
        // 计算等差数列和：(i + ultimo_i) * (ultimo_i - i + 1) / 2，模MOD
        long long sum_a = ((i % MOD) + (ultimo_i % MOD)) % MOD;
        long long cnt = ((ultimo_i - i + 1) % MOD);
        long long s = sum_a * cnt % MOD;
        s = s * INV2 % MOD;
        // 累加 s*q mod MOD
        ans = (ans + s * (q % MOD) % MOD) % MOD;
        i = ultimo_i + 1;
    }

    cout << ans << endl;
    return 0;
}

关键修正点说明：

1. 移除所有floor调用，直接用整数除法n/i和n/q，避免浮点数精度问题。
2. 所有运算分步取模，利用模运算的分配律保证结果在MOD范围内：
   • 等差数列求和时，先对每一项取模，再相乘，最后乘以2的逆元（除法在模运算中等价于乘以逆元）。
3. 每一步累加后都对ans取模，彻底避免溢出问题。

内容的提问来源于stack exchange，提问作者FRANCISCO MÁRQUEZ