很有意思的題目，給定一個數（長達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 閱讀(187)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory