很有意思的题目，给定一个数（长达500000位），问它是不是一个数n的n次幂，如果是，输出n，否则输出-1。还有一个条件是如果不是的话，它只可能有一位写错了，而且数的位数不变。
首先考虑如果确定n，当n大于1的时候，n ^ n的位数是不同的(n * logn)，这样根据输入的长度可以确定n。之后就要考虑怎样检测出这个数是不是正确的。因为只有一位可能有变换，那么就是在原数的基础上多了（或少了）一个k * 10 ^ i，其中k = 1...9，i = 0...n。考察这个数的素因子，只可能是2、3、5、7，这样的话如果我取一个模11，显然k * 10 ^ i模11的值一定不为0，这样的话如果有一位发生了变化，它模11的结果和n ^ n模11的结果肯定不同，根据这个方法我就可以在O(L)的复杂度内检测出这个数是否正确了，L是位数。
实现的时候有一个很容易出错的地方。因为需要预处理出每个n的n次幂的位数，正常的话n * logn向上取整就是答案，但是n是10的整数幂的时候有些特别，是n * logn + 1，需要单独处理（我是加了一个1e-2再向上取整），因为这个原因错了一次，还有一次是输入的字符串大小开小了。
附题目代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int MOD = 11, N = 100001;
int d[N], m[N];
int power_mod(int a, int b)
{
int ret = 1, f = a;
while (b)
{
if (b & 1)
ret = ret * f % MOD;
f = f * f % MOD;
b >>= 1;
}
return ret;
}
void init()
{
int tmp;
for (int i = 2; i < N; i++)
{
tmp = (int)(ceil(i * log(i) / log(10.0) + 1e-2) + 1e-1);
d[i] = tmp;
m[i] = power_mod(i % MOD, i);
}
}
int main()
{
char str[N*5];
int T, p, len, tmp;
init();
scanf("%d", &T);
while (T--)
{
scanf("%s", str);
len = strlen(str);
if (len == 1 && str[0] == '1')
{
puts("1");
continue;
}
p = lower_bound(d, d + N, len) - d;
tmp = 0;
for (int i = 0; i < len; i++)
{
tmp = tmp * 10 + (str[i] - '0');
tmp = tmp % MOD;
}
printf("%d\n", tmp == m[p] ? p : -1);
}
return 0;
}
posted on 2009-06-12 11:15
sdfond 阅读(144)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm - Number Theory