LightOJ 1282 Leading and Trailing

缘起

给定正整数n和k, 要你求出 n^k 的前三位和后三位

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
你有两个整数：n和k，你的任务是找到最重要的三位数，最低三位数的nk。

【输入】
输入以整数T（≤1000）开始，表示测试用例的数量。

每种情况都以包含两个整数的行开始：n（2≤n<2^31）和k（1≤k≤10^7）。

【输出】
对于每种情况，打印案例编号和三个前导数字（最重要）和三个尾随数字（最不重要）。 您可以假设输入是这样的，
即n^k包含至少六位数。

【样例输入】
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

【限制】
Time limit 2000 ms
Memory limit 32768 kB

【1】和【2】其实分别给出了求最高位和最低位的算法. 其实本题就是【1】+【2】嘛~

关于高三位的推导是

令
$$
m=n^k
$$
两边取1000为底的对数
$$
log_{1000}m = k*log_{1000}n
$$
令
$$
x.y = log_{1000}m
$$
x是整数部分, y是小数部分, 则只需要知道 1000^y =a.bc…. 即可

所以求高三位的步骤为

1
2
1. 计算 k*log_{1000}n 的小数部分，令为y
2. 计算 1000^{y}

ac代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
//#define LOCAL
typedef long long LL;

LL n,k;

int hi(LL n,LL k) // 求 n^k 的高三位
{
	double t = k* log(1.0*n)/log(1000.0);
	double y = t-(LL)t;
	double ans = pow(1000.0, y);
	if (ans < 10) // 9.52783443325
	{
		ans *= 100;
	}
	else if (ans < 100) // 95.2783443325
	{
		ans *= 10;
	}
	return (int)ans;
}

LL lo(LL n,LL k) // 求 n^k 的低三位
{
	LL ans = 1;
	n %= 1000;
	while(k)
	{
		if (k&1)
		{
			ans = ans * n % 1000;
		}
		if (k>1)
		{
			n = n *n %1000;
		}
		k>>=1;
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	for (int i = 1; i<=t; i++)
	{
		scanf("%lld%lld", &n, &k);
		printf("Case %d: %-03d %03lld\n", i, hi(n,k), lo(n,k));
	}
	return 0;
}

ac情况如下

Status Accepted
Time 3ms
Memory 1476kB
Length 772
Lang C++
Submitted 2019-08-07 15:36:06
Shared
RemoteRunId 1543844

参考

【1】https://yfsyfs.github.io/2019/08/07/hdu-1060-Leftmost-Digit/

【2】https://yfsyfs.github.io/2019/08/07/hdu-1061-Rightmost-Digit/