1029: 数一的逆袭
题目描述
数一是一个穷屌丝兼程序猿，是社会受剥削的底层人物，但是他有一个梦想，就是博得女神的欢心。这天，数一的女神说:"一直活在二次元的屌丝啊，一直活在二进制的程序猿啊，你们这群二货快告诉我这堆2是怎么回事？"女神已经被2的幂次搞晕过去了，她只是想知道2的n次方的最高位和最低位是多少，你能帮数一逆袭女神吗？
输入
第一行首先是一个正整数T(T<=100)
接下来是T行，每行代表一组数据，每组数据仅有一个正整数n(n<=100000)
输出
对于每组数据，输出两个整数，以空格分隔，分表表示2^n的最高位和最低位
样例输入
5123410
样例输出
2 24 48 81 61 4
提示
来源
题目类型：简单数学
算法分析：2^n的最低位可以通过整数快速幂取模求得，而最高位可由下面推导得来：
res = floor (2^n / 10^(k-1))，则res = floor (10 ^ (log10 2 ^ n – (k – 1)))，其中k = floor (log10 2^n) + 1，即k = floor(nlog10 2) + 1，化简得到res = floor (10 ^ (nlog10 2- floor (nlog10 2)))，注意输出结果时要加上EPS！！！！！！
|
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 100000 + 66; long long Solve (long long a, long long b, long long mod) { long long res = 1, temp = a % mod; while (b) { if (b & 1) res = (res * temp) % mod; temp = (temp * temp) % mod; b >>= 1; } return res; } int main() { // freopen ("aaa.txt", "r", stdin); int t; scanf ("%d", &t); while (t--) { int n; scanf ("%d", &n); printf ("%d %d\n", (int) (pow (10, n * log10 (2) - floor (n * log10 (2))) + EPS), Solve (2, n, 10)); } return 0; } |
- « 上一篇：xdu1028
- xdu1036：下一篇 »