自动搬运

查看原文

来自洛谷，原作者为

	摸鱼 Orz%%%@alpha1022

搬运于2025-08-24 21:27:18，当前版本为作者最后更新于2019-11-07 07:39:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

- 前置知识:

	(a+y)^x=a^x(mod y)

快速幂：比较简单的数论基础，如果没有学过，快速幂传送门

- 当我看到这一题时，我脑子里冒出了两个想法：

1. 这题的快速幂是妥妥的（√）

2. 在吗？模数是不是质数？可不可以套逆元？（×） 然而沙雕的我却忽略了模数那小到可怜的大小，显然这一题必须针对模数进行操作，且时间复杂度与x,y无关，所以：

   a^x 可化为 (a%10000)^x

所以我们只要用一个sum前缀和数组存储前i个数的次方和:

	sum[i]=(sum[i-1]+qpow(i,b))%mod;

然后O(1)求答案：

	ans=n/10000*sum[10000]+sum[n%10000]

详见代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;//同#define LL long long
const LL mod=10000;
LL a,b,ans,sum[10010];
inline LL qpow(LL a,LL p,LL mod){//快速幂模板，求a^p
	LL sum=1;
	while(p){
		if(p&1){
			sum=sum*a%mod;
		}
		a=a*a%mod;
		p>>=1;//通过倍增的方法求幂；
	}
	return sum%mod;
}
int main(){
	LL Time; 
	scanf("%lld",&Time);
	while(Time--){
		scanf("%lld%lld",&a,&b);
		for(register LL i=1;i<=10000;++i){
			sum[i]=(sum[i-1]+qpow(i,b,mod))%mod;//针对模数下手，用数组求出(i<=10000)的前缀和
		}
		ans=(a/10000*sum[10000]+sum[a%10000])%mod;//通过上文所将的前缀和以O(1)求出答案；
		printf("%lld\n",ans);
	}
}

综上所述，预处理O(mod),求值O(1),所以时间复杂度为O(T*mod)，空间复杂度为O(10000)，能够通过评测