本文主要是介绍历届试题 小数第n位--快速幂算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。
输入格式
一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）
输出格式
一行3位数字，表示：a除以b，小数后第n位开始的3位数字。
样例输入
1 8 1
样例输出
125
样例输入
1 8 3
样例输出
500
样例输入
282866 999000 6
样例输出
914
思路：
由于数据的范围很大，如果按照一般的算法进行计算，那么一定会超时；
也不能够用double s=a/b*10^(n+2),数据太大，double的精确度不够，所以我们要找到一个合适的算法进行求解；
最合适的算法就是快速幂算法--反复平方；
快速幂算法--反复平方：
A:
当 X^n=((X^2)^2)......；
如果把n表示为2的幂次的和：n=2^k1+2^k2+2^k3+.....;
那么X^n=(x^2^k1)(x^2^k2)(x^2^k3).......;
时间复杂度就是O(logn);
例如：
x^22=x^16*x^4*x^2; (22转换成二进制是10110）；
ll qq(ll n,ll k)
{ll ret=1;while(k){if(k&1)//如果二进制最低位为1，则乘上n^(2^i);ret=((ret%mod)*(n%mod))%mod;n=(n%mod)*(n%mod);//将n平方；k>>=1;//右移一位，相当于除2；}return ret%mod;
}B:
也可以用另外一种思路来理解；
当n为偶数的时候有X^n=((x^2)^(n/2)),递归转为n/2的情况；
当n为奇数时有X^n=((x^2)^(n/2))*x;同样也递归转为n/2的情况。
这样递归下去，每次n都减半，于是可以在O(logn）时间内完成幂运算；
ll qq(ll n,ll k)
{if(k==0)return 1;ll ret=qq(n*n%mod,k/2);if(k&1)ret=ret*n%mod;return ret%mod;
}代码如下：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;ll a,b,n,mod;ll qq(ll n,ll k)
{ll ret=1;while(k){if(k&1)//如果二进制最低位为1，则乘上n^(2^i);ret=((ret%mod)*(n%mod))%mod;n=(n%mod)*(n%mod);//将n平方；k>>=1;//右移一位，相当于除2；}return ret%mod;
}/*ll qq(ll n,ll k)
{if(k==0)return 1;ll ret=qq(n*n%mod,k/2);if(k&1)ret=ret*n%mod;return ret%mod;
}*/int main()
{while(~scanf("%lld%lld%lld",&a,&b,&n)){mod=b*1000;ll sum=(a%mod*qq(10,n+2))%mod;ll s=sum/b;printf("%lld\n",s);}return 0;
}
这篇关于历届试题 小数第n位--快速幂算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
