很有意思的題目，給定一個(gè)數(shù)（長(zhǎng)達(dá)500000位），問(wèn)它是不是一個(gè)數(shù)n的n次冪，如果是，輸出n，否則輸出-1。還有一個(gè)條件是如果不是的話，它只可能有一位寫(xiě)錯(cuò)了，而且數(shù)的位數(shù)不變。
首先考慮如果確定n，當(dāng)n大于1的時(shí)候，n ^ n的位數(shù)是不同的(n * logn)，這樣根據(jù)輸入的長(zhǎng)度可以確定n。之后就要考慮怎樣檢測(cè)出這個(gè)數(shù)是不是正確的。因?yàn)橹挥幸晃豢赡苡凶儞Q，那么就是在原數(shù)的基礎(chǔ)上多了（或少了）一個(gè)k * 10 ^ i，其中k = 1...9，i = 0...n。考察這個(gè)數(shù)的素因子，只可能是2、3、5、7，這樣的話如果我取一個(gè)模11，顯然k * 10 ^ i模11的值一定不為0，這樣的話如果有一位發(fā)生了變化，它模11的結(jié)果和n ^ n模11的結(jié)果肯定不同，根據(jù)這個(gè)方法我就可以在O(L)的復(fù)雜度內(nèi)檢測(cè)出這個(gè)數(shù)是否正確了，L是位數(shù)。
實(shí)現(xiàn)的時(shí)候有一個(gè)很容易出錯(cuò)的地方。因?yàn)樾枰A(yù)處理出每個(gè)n的n次冪的位數(shù)，正常的話n * logn向上取整就是答案，但是n是10的整數(shù)冪的時(shí)候有些特別，是n * logn + 1，需要單獨(dú)處理（我是加了一個(gè)1e-2再向上取整），因?yàn)檫@個(gè)原因錯(cuò)了一次，還有一次是輸入的字符串大小開(kāi)小了。
附題目代碼：
#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 閱讀(180)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
Algorithm - Number Theory