Power of Cryptography
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 14584 Accepted: 7412
Description
Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers among these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be only of theoretical interest.
This problem involves the efficient computation of integer roots of numbers.
Given an integer n>=1 and an integer p>= 1 you have to write a program that determines the n th positive root of p. In this problem, given such integers n and p, p will always be of the form k to the nth. power, for an integer k (this integer is what your program must find).
Input
The input consists of a sequence of integer pairs n and p with each integer on a line by itself. For all such pairs 1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 such that kn = p.
Output
For each integer pair n and p the value k should be printed, i.e., the number k such that k n =p.
Sample Input
2 16
3 27
7 4357186184021382204544
Sample Output
4
3
1234
如果你只是想知道為什麼double型開n次方法通過的原因，請跳過此部分。
題目大意：
求一個整數k，使得k滿足kn=p。
思路：
由於p的值很大，超出了基本數據類型所表示的范圍，所以采用大數乘法來計算kn，當kn=p時，得出結果（不知道能不能大數開n次方…）。那k值應該如何取呢？根據n和p的關系是可以確定出k的位數的，例如：n=7，p=4357186184021382204544，p的位數為22，用22/7的結果向上取整，得到4，即為k的位數，也就是說k的取值范圍是1000~9999。在這個范圍內進行二分查找，就可以找到滿足條件的k值。（這狗屎題目中說“there exists an integer k, 1<=k<=109 , such that kn = p.”，其實…逗你玩！）
#include <stdio.h>
#include <string.h>
#include <math.h>
#define LENGTH 110
#define LAST LENGTH-2
#define GREATER 1
#define EQUAL 0
#define LESS -1
//大整數相乘
char* IntegerMultiplication(const char *a, const char *b, char *product)
{
int i, j, k = LAST, first, value, temp[LENGTH];
memset(temp, 0, sizeof(temp));
for (i = strlen(a)-1; i >= 0; i--)
{
first = k--;
value = a[i] - '0';
for (j = strlen(b)-1; j >= 0; j--)
{
temp[first--] += value * (b[j] - '0');
}
}
for (i = LAST; i >= first; i--)
{
product[i] = temp[i] % 10 + '0';
temp[i-1] += temp[i] / 10;
}
while (product[first] == '0' && first < LAST)
{
first++;
}
return &product[first];
}
//比較兩個字符串所表示數值的大小
int Compare(char *numA, char *numB)
{
//去除前導'0'
for (; *numA == '0'; numA++);
for (; *numB == '0'; numB++);
int lenNumA = strlen(numA);
int lenNumB = strlen(numB);
if (lenNumA == lenNumB)
{
return strcmp(numA, numB);
}
if (lenNumA > lenNumB)
{
return GREATER;
}
return LESS;
}
//求base^exp，結果存放在res中，pRes指向結果的首位數字的位置
char* Power(char *base, int exp, char *res)
{
res[LAST] = '1';
char *pRes = &res[LAST], *temp = base;
while (exp != 0)
{
if (exp % 2 == 1)
{
pRes = IntegerMultiplication(base, pRes, res);
}
exp /= 2;
if (exp != 0)
{
base = IntegerMultiplication(base, base, temp);
}
}
return pRes;
}
int main(void)
{
char p[LENGTH], res[LENGTH], cMid[LENGTH];
unsigned int n, lenP, lenRoot, i, min, max, mid;
while (scanf("%d %s", &n, &p) != EOF)
{
//根據n和p的倍數關系，得到k的范圍的min值和max值
lenP = strlen(p);
lenRoot = (int)ceil((double)lenP / n);
for (i = 1, min = 1; i < lenRoot; i++)
{
min *= 10;
}
for (i = 1, max = 9; i < lenRoot; i++)
{
max *= 10;
max += 9;
}
//二分法尋找k值
bool finish = false;
while (!finish)
{
mid = (min + max) / 2;
if (min >= max)
{
break;
}
sprintf(cMid, "%d", mid);
memset(res, 0, sizeof(res));
switch (Compare(Power(cMid, n, res), p))
{
case LESS: min = mid + 1; break;
case EQUAL: finish = true; break;
case GREATER: max = mid - 1; break;
default: break;
}
}
//由於題目所給數據會有不滿足k^n=p的情況
//下面是為了得到一個最大的k，滿足k^n<=p
sprintf(cMid, "%d", mid);
if (Compare(Power(cMid, n, res), p) == GREATER)
{
mid--;
}
printf("%d\n", mid);
}
return 0;
}
double型開n次方的方法通過的原因
下面這段程序也是可以通過此題的。
#include<stdio.h>
#include<math.h>
int main(void)
{
double n, p;
while(scanf("%lf%lf", &n, &p) != EOF)
{
printf("%.0lf\n", pow(p, 1/n));
}
return 0;
}
首先，題目中的數據強度並不弱，這一點確實如題目中所說：“For all such pairs 1<=n<= 200, 1<=p<10101，所以，double型是不能精確地表示出所給數據，但是卻能表示出一個近似值。
當向double型變量中存入
4357186184021382204544
然後再輸出，得到的是
4357186184021382000000
後六位的值變為了0，這一點和int型變量是有很大區別的。也就是說當存入double型變量的值超出了它的精度表示范圍時，將低位的數據截斷。（關於浮點數在計算機中的表示方法，百度吧…講的蠻清楚的。）
在本題中，如果測試數據為：
7 4357186184021382204544
實際上所處理數據是：
7 4357186184021382000000
拿4357186184021382000000開7次方的結果自然就是1234。
為什麼不是1233或者1235呢？
12337=4332529576639313702577
12347=4357186184021382204544
12357=4381962969567270546875
可以看出在double型所能表示的精度范圍內，它們三個值已經不同了。
所以，此題中的測試數據也都是類似於上述情況，所以才能使用double型開n次方的方法。
