随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 2720 Last Digits

题目链接: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, 
-1sizeof(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;
}

posted on 2011-04-07 20:02 英雄哪里出来 阅读(1362) 评论(0)  编辑 收藏 引用 所属分类: 数学


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理