首页 > 代码库 > UVA - 11029Leading and Trailing(快速幂取模取后三位 + log10()取前三位)
UVA - 11029Leading and Trailing(快速幂取模取后三位 + log10()取前三位)
题目: UVA - 11029Leading and Trailing(快速幂取模取后三位 + log10()取前三位)
题目大意:给你N的k次方,然后要求你求出这个数的前三位和后三位。
解题思路:因为n和k都很大,这个数求出来是大数,所以可以用快速幂取模求后三位,因为后面的三位和前面的位数的没有关系。前面的三位比较难办。设x = log (n^k) = k * log10(n),那么10^x = k * log10(n).将X = a(整数) + b(小数),整数部分10^a只是移动小数点,并不影响前三位。所以只需要求出10^b取前三位。用fmod(a, 1)表示求a的小数部分。
代码:
#include <cstdio> #include <cmath> using namespace std; int num, k; int f(int d) { if (d == 1) return num % 1000; if (d == 0) return 1; int n = f(d / 2) % 1000; n = (n * n) % 1000; if (d % 2) n = (n * (num % 1000)) % 1000;//注意num要%1000,不然会爆int return n; } int main () { int T; scanf ("%d", &T); while (T--) { scanf ("%d%d", &num, &k); int tail = f(k); int head = (int)pow (10, 2 + fmod (k * log10(num * 1.0), 1.0)); printf ("%d...%03d\n", head, tail); } return 0; }
UVA - 11029Leading and Trailing(快速幂取模取后三位 + log10()取前三位)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。