华师一附中OI组
标题:
P1630 求和
[打印本页]
作者:
admin
时间:
2018-6-28 14:44
标题:
P1630 求和
https://www.luogu.org/problemnew/show/P1630
题目描述
求1^b+2^b+……+a^b的和除以10000的余数。
输入输出格式
输入格式：
第一行包含一个正整数N，表示共有N组测试数据；
接下来N行，每行包含两个正整数a和b。
【数据规模】
对于30%的数据中，满足N<=10，a,b<=1000;
对于100%的数据中，满足N<=100，a,b<=1000000000;
输出格式：
共N行，每行一个对应的答案。
输入输出样例
输入样例#1：
1
2 3
输出样例#1：
9
作者:
admin
时间:
2018-6-28 14:58
最笨的方法，直接求a^b，保留他的最后四位数，累加。
#include<iostream>
using namespace std;
int n,a,b;
int i,j,s,t;
int main()
{
cin>>n;
while (n--)
{
cin>>a>>b;
s=0;
for (i=1; i<=a; i++)
{
t=1;
for (j=1; j<=b; j++) t=(t*i)%10000;
s=(s+t)%10000;
}
cout<<s%10000<<endl;
}
return 0;
}
复制代码
作者:
admin
时间:
2018-6-28 15:03
以上代码1,3,4正确，其他超时，得分30 ，我们要想另外的做法，优化的地方有两个，
一，快速幂，a^b没有必要把a连乘b次，参考。
修改代码如下：
#include<iostream>
using namespace std;
int n,a,b;
int i,j,s,t,bb,tt;
int main()
{
cin>>n;
while (n--)
{
cin>>a>>b;
s=0;
for (i=1; i<=a; i++)
{
t=1;bb=b;tt=i;
while (bb>0)
{
if (bb%2==1) t=(t*tt)%10000;
bb=bb/2;tt=(tt*tt)%10000;
}
s=(s+t)%10000;
}
cout<<s%10000<<endl;
}
return 0;
}
复制代码
作者:
admin
时间:
2018-6-28 15:12
交上去之后依然改善不明显，我们再次发现，1和10001的b次方末尾的四位数字是一样的，所以我们计算整万的末尾四位数，直接累加，最后不整万的部分独立计算就行了。
#include<iostream>
using namespace std;
int n,a,b;
int i,j,s,t,bb,tt;
int ksm(int a,int b)
{
int t=1,tt=a;
int bb=b;
while (bb>0)
{
if (bb%2==1) t=(t*tt)%10000;
tt=(tt*tt)%10000,bb=bb/2;
}
return t%10000;
}
int s09999()
{
int s=0;
for (i=0;i<=9999;i++)
s=(s+ksm(i,b))%10000;
return s;
}
int main()
{
cin>>n;
while (n--)
{
cin>>a>>b;
s=s09999();
s=s*(a/10000);a=a%10000;
for (i=1; i<=a; i++)
s=(s+ksm(i,b))%10000;
cout<<s%10000<<endl;
}
return 0;
}
复制代码
作者:
admin
时间:
2018-6-28 15:13
一边讲，一边做给同学们看，到此，此题AC。。很高兴！花时不到10分钟。状态还不错。
作者:
admin
时间:
2018-6-28 15:19
我来给大家估算时间复杂度：
第一种方法，硬乘以，硬加，那么应该要做a*b次乘法和a次加法，取模只有1次，就算了。
第二种方法，巧乘，硬加，那么应该要做a*log（b）次乘法和a次加法，基本上少了不少，应该有效果，但此题出题者数据出的不好。
第二种方法，巧乘，巧加，那么应该要做（20000）*log（b）次乘法和。
作者:
admin
时间:
2018-6-28 15:25
没有理解的同学，你请想一想：
1、1+2+3+4+****78 最末尾的数字是几？
2、1^2+2^2+3^2+****78^2最末尾的数字是几？
在扩展到此题
欢迎光临 华师一附中OI组 (http://hsyit.cn/)
Powered by Discuz! X3.2