|
|
题目链接：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;
}
|