P1630 求和

admin

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

最笨的方法，直接求a^b，保留他的最后四位数，累加。

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a,b;
   
4. int i,j,s,t;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     while (n--)
   
9.     {
   
10.         cin>>a>>b;
    
11.         s=0;
    
12.         for (i=1; i<=a; i++)
    
13.         {
    
14.             t=1;
    
15.             for (j=1; j<=b; j++) t=(t*i)%10000;
    
16.             s=(s+t)%10000;
    
17.         }
    
18.         cout<<s%10000<<endl;
    
19.     }
    
20.     return 0;
    
21. }
    

复制代码

admin

以上代码1,3,4正确，其他超时，得分30 ，我们要想另外的做法，优化的地方有两个，
一，快速幂，a^b没有必要把a连乘b次，参考。
修改代码如下：

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a,b;
   
4. int i,j,s,t,bb,tt;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     while (n--)
   
9.     {
   
10.         cin>>a>>b;
    
11.         s=0;
    
12.         for (i=1; i<=a; i++)
    
13.         {
    
14.             t=1;bb=b;tt=i;
    
15.             while (bb>0)
    
16.             {
    
17.                 if (bb%2==1) t=(t*tt)%10000;
    
18.                     bb=bb/2;tt=(tt*tt)%10000;
    
19.             }
    
20.             s=(s+t)%10000;
    
21.         }
    
22.         cout<<s%10000<<endl;
    
23.     }
    
24.     return 0;
    
25. }
    

复制代码

admin

交上去之后依然改善不明显，我们再次发现，1和10001的b次方末尾的四位数字是一样的，所以我们计算整万的末尾四位数，直接累加，最后不整万的部分独立计算就行了。

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a,b;
   
4. int i,j,s,t,bb,tt;
   
5. int ksm(int a,int b)
   
6. {
   
7.     int t=1,tt=a;
   
8.     int bb=b;
   
9.     while (bb>0)
   
10.     {
    
11.         if (bb%2==1) t=(t*tt)%10000;
    
12.         tt=(tt*tt)%10000,bb=bb/2;
    
13.     }
    
14.     return t%10000;
    
15. }
    
16. int s09999()
    
17. {
    
18.     int s=0;
    
19.     for (i=0;i<=9999;i++)
    
20.         s=(s+ksm(i,b))%10000;
    
21.         return s;
    
22. }
    
23. int main()
    
24. {
    
25.     cin>>n;
    
26.     while (n--)
    
27.     {
    
28.         cin>>a>>b;
    
29.         s=s09999();
    
30.         s=s*(a/10000);a=a%10000;
    
31.         for (i=1; i<=a; i++)
    
32.             s=(s+ksm(i,b))%10000;
    
33.         cout<<s%10000<<endl;
    
34.     }
    
35.     return 0;
    
36. }
    

复制代码

admin

一边讲，一边做给同学们看，到此，此题AC。。很高兴！花时不到10分钟。状态还不错。

admin

我来给大家估算时间复杂度：
第一种方法，硬乘以，硬加，那么应该要做a*b次乘法和a次加法，取模只有1次，就算了。
第二种方法，巧乘，硬加，那么应该要做a*log（b）次乘法和a次加法，基本上少了不少，应该有效果，但此题出题者数据出的不好。
第二种方法，巧乘，巧加，那么应该要做（20000）*log（b）次乘法和。

admin

没有理解的同学，你请想一想：
1、1+2+3+4+****78 最末尾的数字是几？
2、1^2+2^2+3^2+****78^2最末尾的数字是几？
在扩展到此题