CSU - 1556 Jerry's trouble(快速幂取模)

CSU - 1556 Jerry's trouble(快速幂取模)

【题目链接】：​​click here​​

【题目大意】：计算x1^m+x2^m+..xn^m(1<=x1<=n)（ 1 <= n < 1 000 000, 1 <= m < 1000）

【解题思路】：快速幂取模

代码：

solution one:

#include#define LL long longusing namespace std;const LL mod=(LL)1e9+7;LL pow_mod(LL a,LL p,LL n){ if(p==0) return 1; LL ans=pow_mod(a,p/2,n); ans=ans*ans%n; if(p&1) ans=ans*a%n; return ans;}int n,m;int main(){ while(scanf("%d%d",&n,&m)!=EOF) { LL s=0; for(int i=1; i<=n; i++) s=(s+pow_mod(i%mod,m,mod))%mod; printf("%lld\n",s); } return 0;}

solution two:

#include #include #include #include using namespace std;typedef long long LL;const LL mod=1e9+7;LL pow_mod(LL a,LL b){ LL res=a,ans=1; while(b) { if(b&1) ans=(res*ans)%mod; res=res*res%mod; b>>=1; } return ans;}int main(){ LL n,m; while(~scanf("%lld %lld",&n,&m)) { LL s=0; for(int i=1; i<=n; ++i) s+=pow_mod(i%mod,m)%mod; printf("%lld\n",s%mod); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。