LightOJ - 1282(n^k的前三位数字和后三位数字)
程序员文章站
2022-07-13 14:00:10
...
You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).
Output
For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that nk contains at least six digits.
Sample Input
5
123456 1
123456 2
2 31
2 32
29 8751919
Sample Output
Case 1: 123 456
Case 2: 152 936
Case 3: 214 648
Case 4: 429 296
Case 5: 665 669
题意如标题
后三位好说,快速幂取个模
前三位我们可以这样:直接作为正整数n^k来取很难,因为这个数会很大并且无法舍去后面的数字来做优化,我们可以转化为小数:
log10(n^k)=k*log10(n),然后又因为n^k=z*10^x,即有log10(n^k)=log10(z)+x,并且在n^k=z*10^x中,x(即10^x)只贡献了该整数的位数,真正的前三位
都被实数z贡献了。
所以有10^(log10(z))的个位和小数点后两位即是n^k的前三位(因为是用科学计数法的,所以z肯定有且只有一个整数位,即只有个位,其余都是小数位)
所以根据式子log10(z)=(double)k*log10(n)-(LL)k*log10(n)即可
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).
Output
For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that nk contains at least six digits.
Sample Input
5
123456 1
123456 2
2 31
2 32
29 8751919
Sample Output
Case 1: 123 456
Case 2: 152 936
Case 3: 214 648
Case 4: 429 296
Case 5: 665 669
题意如标题
后三位好说,快速幂取个模
前三位我们可以这样:直接作为正整数n^k来取很难,因为这个数会很大并且无法舍去后面的数字来做优化,我们可以转化为小数:
log10(n^k)=k*log10(n),然后又因为n^k=z*10^x,即有log10(n^k)=log10(z)+x,并且在n^k=z*10^x中,x(即10^x)只贡献了该整数的位数,真正的前三位
都被实数z贡献了。
所以有10^(log10(z))的个位和小数点后两位即是n^k的前三位(因为是用科学计数法的,所以z肯定有且只有一个整数位,即只有个位,其余都是小数位)
所以根据式子log10(z)=(double)k*log10(n)-(LL)k*log10(n)即可
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=2e5+3;
LL n,k;
LL quick(LL x,LL a)
{
LL res=1,MOD=1000;
while(a)
{
if(a&1)res=x*res%MOD;
x=x*x%MOD;
a>>=1;
}
return res%MOD;
}
int main()
{
int T;
scanf("%d",&T);
int cas=0;
while(T--)
{
scanf("%lld%lld",&n,&k);
LL a1,a2=quick(n,k),z=k*log10(n);
double x=k*log10(n)-(double)z;
x=pow(10,x)*100;//printf("z=%lld x=%f\n",z,x);
a1=x;
printf("Case %d: %lld ",++cas,a1);
if(a2>=100)printf("%lld\n",a2);
else if(a2>=10)printf("0%lld\n",a2);
else printf("00%lld\n",a2);
}
return 0;
}
上一篇: C 语言 写一个函数判断是不是闰年
下一篇: Java学习第二天