【LightOJ】1282 - Leading and Trailing（快速幂 & 数论）
【LightOJ】1282 - Leading and Trailing（快速幂 & 数论）
点击打开题目
1282 - Leading and Trailing
PDF (English) | Statistics | Forum |
|---|
Time Limit: 2 second(s) | Memory Limit: 32 MB |
|---|
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 | Output for Sample Input |
|---|---|
5 123456 1 123456 2 2 31 2 32 29 8751919 | Case 1: 123 456 Case 2: 152 936 Case 3: 214 648 Case 4: 429 296 Case 5: 665 669 |
求n的k次幂的前三位和后三位。
前三位用log的方法求，后三位跑一次快速幂就行。
注意后三位的输出，不够要补齐前导0。
代码如下：
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
#define PI acos(-1)
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define LL long long
LL quick(LL a,LL b)
{
a %= 1000;
LL ans = 1;
while (b)
{
if (b & 1)
ans = ans * a % 1000;
a = a * a % 1000;
b >>= 1;
}
return ans;
}
int main()
{
LL n,k;
int u;
int Case = 1;
scanf ("%d",&u);
while (u--)
{
scanf ("%lld %lld",&n,&k);
printf ("Case %d: ",Case++);
double t = (double)k * (log10(n));
t -= (LL)t;
t = pow(10,t);
t = (LL)(t*100);
LL ans1 = t;
LL ans2 = quick(n,k);
printf ("%lld ",ans1);
/*if (ans2 < 10)
printf ("00%lld\n",ans2);
else if (ans2 < 100)
printf ("0%lld\n",ans2);
else
printf ("%lld\n",ans2);*/
printf ("%03lld\n",ans2); //这样输出更方便
}
return 0;
}腾讯云开发者
