【洛谷P1630】求和

朱雀 2023-06-05 08:55 116阅读 0赞

# Description #

[【LuoguP1630】求和][LuoguP1630]

给定$a,b$，求$(\\sum\\limits\_\{i=1\}^\{a\}\{i^b\})\\mod 10000$

多组询问，$a,b\\le 1e9$

# Solution #

前缀和+快速幂

如果暴力计算答案，那么时间复杂度为$O(Tab)$

使用快速幂优化，那么时间复杂度为$O(Ta\\log b)$

考虑这样一个式子：$$i^b\\mod n=(i\\mod n)^b$$

那么我们就可以预处理出$i^b,i\\in\[0,9999\]$的值，那么时间复杂度变成了$O(Ta)$

考虑每个$i^b\\mod 10000$的值，发现整个序列就是$i^b,i\\in\[0,9999\]$重复了$\\lfloor\\frac\{a\}\{10000\}\\rfloor$次，再加上最后剩下的$i^b,i\\in\[0,9999\]$的前$a\\mod 10000$个数

那么我们就可以处理出$i^b\\mod 10000$的前缀和，然后在预处理完成之后$O(1)$即可完成

这样时间复杂度就变成了$O(T\\times 10000\\times \\log b)$

# Code #

#include <bits/stdc++.h>
    // check if it is judged online
    
    namespace shl {
        typedef long long ll;
        inline ll read() {
            ll ret = 0, op = 1;
            char c = getchar();
            while (!isdigit(c)) {
                if (c == '-') op = -1;
                c = getchar();
            }
            while (isdigit(c)) {
                ret = ret * 10 + c - '0';
                c = getchar();
            }
            return ret * op;
        }
        int T;
        int a, b;
        ll c[10010], sum[10010];
        const int mod = 1e4;
        ll qpow(ll x, ll y) {
            ll ret = 1;
            while (y) {
                if (y & 1) ret = (ret * x) % mod;
                x = x * x % mod;
                y >>= 1;
            }
            return ret;
        }
        int main() {
            T = read();
            while (T--) {
                a = read(), b = read();
                for (register int i = 0; i < 10000; ++i) {
                    c[i] = qpow(i, b);
                    if (i == 0) sum[i] = c[i];
                    else sum[i] = sum[i - 1] + c[i];
                }
                printf("%lld\n", ((sum[mod - 1] * (a / mod) % mod) + sum[a % mod]) % mod);
            }
            return 0;
        }
    }
    int main() {
    #ifdef LOCAL
        freopen("textname.in", "r", stdin);
        freopen("textname.out", "w", stdout);
    #endif
        shl::main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11574307.html

[LuoguP1630]: https://www.luogu.org/problem/P1630