P1630 求和网页链接P1630 求和题目描述求1 b 2 b ⋯ a b 1^b2^b\cdots a^b1b2b⋯ab的和除以10 4 10^4104的余数。输入格式本题有多组数据。第一行一个整数N NN表示共有N NN组测试数据。对于每组数据一行两个整数a , b a,ba,b。输出格式对于每组数据一行一个整数表示答案。输入输出样例 #1输入 #11 2 3输出 #19说明/提示对于30 % 30\%30%的数据N ≤ 10 N \le 10N≤10a , b ≤ 10 3 a,b \le 10^3a,b≤103。对于100 % 100\%100%的数据1 ≤ N ≤ 100 1 \le N \le 1001≤N≤1001 ≤ a , b ≤ 10 9 1 \le a,b \le 10^91≤a,b≤109。解题思路本题是循环节 前缀和优化的求和取模问题。要求计算S ∑ i 1 a i b m o d 10000 S \sum_{i1}^{a} i^b \bmod 10000S∑i1a​ibmod10000其中a , b a,ba,b可达10 9 10^9109多组询问。1. 问题等价转化由于模数为10000 1000010000底数i ii对10000 1000010000取模后( i 10000 ) b ≡ i b ( m o d 10000 ) (i10000)^b \equiv i^b \pmod{10000}(i10000)b≡ib(mod10000)。因此序列i b m o d 10000 i^b \bmod 10000ibmod10000关于i ii每隔10000 1000010000项循环一次。我们只需预处理一个完整周期1 ∼ 10000 1 \sim 100001∼10000的i b m o d 10000 i^b \bmod 10000ibmod10000的前缀和然后对任意a aaS ⌊ a 10000 ⌋ × sum [ 10000 ] sum [ a m o d 10000 ] ( m o d 10000 ) S \left\lfloor \frac{a}{10000} \right\rfloor \times \text{sum}[10000] \text{sum}[a \bmod 10000] \pmod{10000}S⌊10000a​⌋×sum[10000]sum[amod10000](mod10000)其中sum [ i ] ∑ j 1 i ( j m o d 10000 ) b m o d 10000 \text{sum}[i] \sum_{j1}^{i} (j \bmod 10000)^b \bmod 10000sum[i]∑j1i​(jmod10000)bmod10000。2. 算法实现对每组询问( a , b ) (a,b)(a,b)预计算前缀和数组s[0..10000]其中s[i] s[i-1] qpow(i % 10000, b, 10000)并取模。计算ans (a / 10000 % 10000 * s[10000] % 10000 s[a % 10000]) % 10000。注意a / 10000可能很大但在计算时直接与s[10000]相乘再对10000 1000010000取模即可因为s[10000]已经对10000 1000010000取模乘积不会溢出long long。使用快速幂qpow计算底数的b bb次方模10000 1000010000复杂度O ( log ⁡ b ) O(\log b)O(logb)。3. 复杂度分析时间复杂度每组数据预处理O ( 10000 log ⁡ b ) O(10000 \log b)O(10000logb)共有N ≤ 100 N \le 100N≤100组总运算量约100 × 10000 × 30 3 × 10 7 100 \times 10000 \times 30 3\times 10^7100×10000×303×107可以接受。空间复杂度O ( 10000 ) O(10000)O(10000)存储前缀和数组。总结利用模10000 1000010000下底数的周期性将大规模求和拆分为完整周期与余数部分结合前缀和与快速幂实现O ( 10000 log ⁡ b ) O(10000 \log b)O(10000logb)的每组回答。该方法适用于模数较小、指数很大的情况。代码简要说明qpow(a,b,p)快速幂取模返回a b m o d p a^b \bmod pabmodp。主循环读入T TT组数据对每组a , b a,ba,b预处理前缀和数组s。输出((a/10000)*s[10000] s[a%10000]) % 10000。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MOD10000;ll s[10005],T,A,B;inlinellqpow(ll a,ll b,ll p){ll r1;while(b0){if(b1)rr*a%p;aa*a%p;b1;}returnr;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinT;while(T--){cinAB;for(ll i1;iMOD;i)s[i]s[i-1]qpow(i%MOD,B,MOD);cout((A/MOD*s[MOD])%MODs[A%MOD])%MODendl;}return0;}