SPOJ ZSUM问题调试求助：Binary Exponentiation实现结果异常排查

问题根源 #

1. 未全程取模导致数值溢出
   • Z函数累加求和时未对中间结果s取模，i^i增长极快，很快超出long long存储范围引发溢出，最终输出错误大数。
   • 最终计算表达式未取模，且减法可能产生负数，直接输出不符合题目要求。
2. 语法错误：using ll long long应为using ll = long long;或typedef long long ll;，否则编译报错。

修复后的代码 #

#define MOD 1000000007ll
using ll = long long;

ll binAdd(ll a, ll b) {
    ll res = 0;
    a %= MOD;
    while (b) {
        if (b & 1)
            res = (res + a) % MOD;
        a = (a + a) % MOD;
        b >>= 1;
    }
    return res;
}

ll binPow(ll a, ll b) {
    a %= MOD;
    ll res = 1;
    while (b) {
        if (b & 1)
            res = binAdd(res, a);
        a = binAdd(a, a);
        b >>= 1;
    }
    return res;
}

ll Z(ll n, ll k) {
    ll s = 0;
    for (ll i = 1; i <= n; i++) {
        s = (s + binPow(i, k)) % MOD;
    }
    for (ll i = 1; i <= n; i++) {
        s = (s + binPow(i, i)) % MOD;
    }
    return s;
}

void solve() {
    ll n, k;
    while (cin >> n >> k && (n != 0 || k != 0)) {
        ll zn = Z(n, k);
        ll zn1 = (n >= 1) ? Z(n-1, k) : 0;
        ll zn2 = (n >= 2) ? Z(n-2, k) : 0;
        ll ans = (zn + zn1 - 2 * zn2) % MOD;
        // 处理负数结果
        if (ans < 0) ans += MOD;
        cout << ans << endl;
    }
}

关键修复点 #

• 累加过程取模：Z函数中每次将binPow结果累加到s时，立即对MOD取模，彻底避免数值溢出。
• 最终结果修正：计算后先取模，若结果为负则加上MOD，确保输出为非负的模后结果。
• 边界与类型修正：处理n<1或n<2的边界情况，将循环变量i改为ll类型，避免与n的类型不匹配问题。
• 语法修正：修正using声明的语法错误，保证代码可编译。

内容的提问来源于stack exchange，提问作者Nik