|
|
題目鏈接：http://poj.org/problem?id=2720
  /**//*
 題意：
給定三個整數 b, n, 和 i, 定義函數 f(x) = b^f(x-1) 如果 x > 0, 并且 f(0)=1。
要求計算 f(i) 的最后n為十進制整數，并且要求輸出前導零。
解法：
二分求冪 + 歐拉函數 + 素數篩選
思路：
除非b等于1的時候，否則，這個數列的增長速度很快，所以直接暴力是行不通的，這
里我們用到數論的一個結論，a^b % c = a^ (b % phi(c) + phi(c)) % c，b < phi(c)。
其中phi(c)是c的歐拉函數，也就是小于等于c并且與之互質的數的個數。
于是當b比較小的時候就可以直接采用二分求冪來做，當b很大的時候就利用這個結論
，可以迅速將指數降下來。
這題是海量數據，如果每個數都直接算肯定會超時，我的做法是用一個數組保存下來
，而且保存的是n等于7的值，也就是保存了整數后7為，這樣可以少算6倍。最后再做處理
，注意前導零的處理。
 */
#include <iostream>
using namespace std;
#define maxn 3163
bool f[maxn];
int prime[maxn], size;
int ten[8];
void Init()  {
int i, j;
f[0] = f[1] = 1;
  for(i = 2; i < maxn; i++) {
if(!f[i]) {
prime[size++] = i;
for(j = i+i; j < maxn; j += i) {
f[j] = 1;
 }
}
}
ten[0] = 1;
for(i = 1; i <= 7; i++) {
ten[i] = ten[i-1] * 10;
}
}
int phi(int v) {
int i;
int ans = 1;
for(i = 0; i < size; i++) {
if(!(v % prime[i])) {
v /= prime[i];
while(!(v % prime[i])) {
v /= prime[i];
ans *= prime[i];
}
ans *= prime[i] - 1;
if(v == 1)
return ans;
}
}
return ans * (v - 1);
}
int Product_Mod(int a, int b, int mod) {
int S = 0;
while(b) {
if(b & 1) {
S = (S + a) % mod;
}
b >>= 1;
a = (a + a) % mod;
}
return S;
}
#define ll __int64
int Exp_Mod(ll a, int b, int mod) {
ll v = 1;
while(b) {
if(b & 1) {
v *= a;
if(v >= mod)
v %= mod;
}
b >>= 1;
a *= a;
if(a >= mod)
a %= mod;
}
return v;
}
int hash[101][101];
int F[101][101];
int dfs(int b, int n, int mod) {
if(n == 0)
return 1 % mod;
if(mod == 1)
return 0;
if(F[b][n] < 0) {
int oula = phi(mod);
return Exp_Mod( b, dfs(b, n-1, oula) + oula, mod);
}else {
return F[b][n] % mod;
}
}
int Test(int b, int ex) {
if(ex < 0)
return -1;
int i;
int sum = 1;
for(i = 0; i < ex; i++) {
sum *= b;
if(sum >= ten[7])
return -1;
}
return sum;
}
int main() {
Init();
int i, j;
int bew, n, mod, ans;
memset(hash, -1, sizeof(hash));
for(i = 1; i <= 100; i++) {
F[i][0] = 1;
for(j = 1; j <= 100; j++) {
F[i][j] = Test(i, F[i][j-1]);
}
}
while(scanf("%d", &bew) != EOF && bew) {
scanf("%d %d", &n, &mod);
if(hash[bew][n] == -1) {
if(bew == 1) {
ans = 1;
}else {
ans = dfs(bew, n, ten[7]);
}
hash[bew][n] = ans;
}
ans = hash[bew][n] % ten[mod];
for(i = 1; i <= 7; i++) {
if(ans < ten[i]) {
break;
}
}
for(i = mod-i; i ; i--) {
printf("0");
}
printf("%d\n", ans);
}
return 0;
}
|