首页 > 代码库 > [题解]UVA11029 Leading and Trailing

[题解]UVA11029 Leading and Trailing

2024-07-10 07:20:58   219人阅读

链接：http://vjudge.net/problem/viewProblem.action?id=19597

描述：求n^k的前三位数字和后三位数字

思路：题目要解决两个问题。后三位数字可以一边求高次幂一边取模，下面给出求前三位数字的方法。

        n^k = (10^lg n)^k = 10^(k*lg n)

        为了描述方便，令X=n^k 。则 lg X 的整数部分表示X有多少位。设整数部分为zs，小数部分为xs，则X=(10^zs)*(10^xs) 。 (10^zs)的形式就是100……，跟X的位数一样，那么(10^xs)就是在100……的基础上修饰每一位上的数字，使之成为X。那么(10^xs)*100就是X的前三位（没想清楚的朋友可以在纸上划一划）。

 

下面给出我的实现。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 using namespace std; 5 #define MOD 1000 6 int T,N,K; 7 int Trail; 8 double Lead; 9 inline void Get_int(int &Ret)10 {11     char ch;12     bool flag=false;13     for(;ch=getchar(),ch<‘0‘||ch>‘9‘;)14         if(ch==‘-‘)15             flag=true;16     for(Ret=ch-‘0‘;ch=getchar(),ch>=‘0‘&&ch<=‘9‘;Ret=Ret*10+ch-‘0‘);17     flag&&(Ret=-Ret);18 }19 int My_Pow(int n,int k)20 {21     if(k==1)22         return n%MOD;23     int p=My_Pow(n,k/2);24     if(k%2)25         return (p*p*(n%MOD))%MOD;26     return (p*p)%MOD;27 }28 int main()29 {30     Get_int(T);31     while(T--)32     {33         Get_int(N);Get_int(K);34         Lead=(double)K*log10(N);35         Lead=Lead-(int)Lead;36         Lead=pow((double)10,2+Lead);37         Trail=My_Pow(N,K);38         printf("%d...%03d\n",(int)Lead,Trail);39     }40     return 0;41 }
View Code

 


联系
我们