首页 > 代码库 > poj 2109 Power of Cryptography
poj 2109 Power of Cryptography
题目链接：
http://poj.org/problem?id=2109
题目描述：
给n，p。肯定有k(1<=k<=109)，满足kn=p，1<=n<=200,1<=p<=10101,问k是几？
解题思路：
由于p太大，无法对p进行开方，只有枚举k，又因为k太大又知道k的范围，所以很自然就想到了二分枚举，大树乘法加上二分枚举就可以解决。^_^……（奉上代码）！！
代码：
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #define INF 1000000000 6 #define N 110 7 8 int a[N], b[N], n, len; 9 char str[N];10 int judge (int x);11 int main ()12 {13 int i, low, high, mid;14 while (scanf ("%d %s", &n, str) != EOF)15 {16 memset (a, 0, sizeof(a));17 len = strlen (str);18 for (i=0; i<len; i++)19 a[i] = str[i] - ‘0‘;20 21 low = 1;22 high = INF;23 24 while (low <= high)25 {26 mid = (low + high) / 2;27 int m = judge (mid);28 if (m < 0)29 low = mid + 1;30 else if (m > 0)31 high = mid - 1;32 else33 break;34 }35 printf ("%d\n", mid);36 }37 return 0;38 }39 40 int judge (int x)41 {42 int m , i, j;43 m = n * log10(x) + 1;44 if (m > len)45 return 1;46 else if (m < len)47 return -1;48 else49 {50 memset (b, 0, sizeof(b));51 b[0] = 1;52 for (i=0; i<n; i++)53 {54 int yu = 0;55 for (j=0; j<110; j++)56 {57 int s = x * b[j] + yu;58 b[j] = s % 10;59 yu = s / 10;60 }61 }62 for (i=0; i<len; i++)63 if (b[len-1-i] > a[i])64 return 1;65 else if (b[len-1-i] < a[i])66 return -1;67 return 0;68 }69 }
poj 2109 Power of Cryptography
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。