华师一附中OI组

标题: 1^n+2^n+3^n+****m^n的最后k位数 [打印本页]

---

作者: admin    时间: 2018-5-1 14:45
标题: 1^n+2^n+3^n+****m^n的最后k位数
这是湖南某年的一个训练题，高精度乘幂和加法，要做很容易，要得高分不容易，我总拿来做基础班的训练题，考察大家代码的控制能力。

---

作者: admin    时间: 2018-5-1 14:46
沙发自己抢。此题要想出结果很简单，不用高精度也可以对付10-20位以下的数值，可以写一个用来对拍。但是mnk大约到几百的时候就不行了，优化的技巧很考验人的编程能力和分析能力。当n比较小的时候，快速幂没有太大的必要。甚至单精度乘速度更快。
当k比较小的时候，压位优势就不明显。
当m比较小的时候，就直接计算m^n不需要保存先前的计算结果。
总之，此题很值得一做。
我没有压位，参考程序

1. //1^n+2^n+****m^n最后k位
   
2. #include<iostream>
   
3. #include<iomanip>
   
4. using namespace std;
   
5. int a[1000][1000],s[1000],t[1000];
   
6. //a是单个m^n的值，s是总和，t是临时计算的值
   
7. int maxp;
   
8. int m,n,k;
   
9. int i,j;
   
10. void mul(int a[],int b[]) //a=a*b的高精度形式
    
11. {
    
12.     int i,j,x;
    
13.     int c[1000];
    
14.     for (i=0; i<=999; i++) c[i]=0;
    
15.     for(i=0; i<=k-1; i++)
    
16.         for(j=0; j<=k-i-1; j++) c[i+j]+=a[i]*b[j];
    
17.     for(i=0; i<=k-2; i++)
    
18.     {
    
19.         x=c[i];
    
20.         c[i]=x%10;
    
21.         c[i+1]+=x/10;
    
22.     }
    
23.     for(i=0; i<=k-1; i++)a[i]=c[i];
    
24. }
    
25. void pow(int a[],int m,int n) //a=m^n的高精度形式
    
26. {
    
27.     int i,j,x;
    
28.     int ss[1000];
    
29.     for (i=0; i<=999; i++) ss[i]=a[i]=0;
    
30.     ss[0]=m;a[0]=1;
    
31.     while (n>0)
    
32.     {
    
33.         if (n%2==1) mul(a,ss);
    
34.         n=n/2;mul(ss,ss);
    
35.     }
    
36. }
    
37. 
    
38. int main()
    
39. {
    
40.     cin>>m>>n>>k;
    
41.     for (i=2; i<=m; i++)
    
42.     {
    
43.         j=2;while (i%j!=0) j++;
    
44.         if (j==i)
    
45.         {
    
46.             pow(s,j,n);
    
47.         }
    
48.         else
    
49.         {
    
50.             for (int jj=0; jj<=k-1; jj++)
    
51.             {
    
52.                 s[jj]=a[j][jj];
    
53.                 t[jj]=a[i/j][jj];
    
54.             }
    
55.             mul(s,t);
    
56.         }
    
57.         for (int jj=0; jj<=k-1; jj++) a[i][jj]=s[jj];
    
58. 
    
59.         //for (j=k-1; j>=0; j--) cout<<a[i][j];cout<<endl; 输出每个单项的值
    
60.     }
    
61.     //把 a 加到s
    
62.     s[0]=1;for (i=1;i<=k-1;i++) s[i]=0;
    
63.     for (j=1; j<=m; j++)
    
64.         for (i=0;i<=k-1;i++) s[i]=s[i]+a[j][i];
    
65.     //处理s的进位
    
66.     for (i=0;i<=k-2;i++) {int x=s[i];s[i]=x%10;s[i+1]=s[i+1]+x/10;}
    
67.     //输出
    
68.     for (j=k-1; j>=0; j--) cout<<s[j];
    
69. 
    
70.     /*对拍验算
    
71.     cout<<"======\n";
    
72.     long long pp=0,ss=0,tt=0;
    
73.     for (m=1;m<=10;m++)
    
74.     {ss=1;for (n=1;n<=10;n++) ss=ss*m;tt=tt+ss;}
    
75.     cout<<tt;
    
76.     */
    
77. 
    
78.     return 0;
    
79. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2