POJ-2720 : Last Digits

問題概要

f(0)=1, f(n)=b^f(n-1)のとき、f(i)の下n桁を求める問題。n<=7,b<100。

解法

b^kをmod mで見るとρのように尻尾とループの部分ができる。ループの部分の長さはphi(m)の約数になるので、ループの部分の長さはphi(m)だと思ってよい。最終的にb^k mod mが知りたいとき、k mod phi(m)の値が分かっていればよい。この問題ではkがb^tの形をしているのでk mod phi(m)を知るにはt mod phi(phi(m))の値が分かっていればよい…とphi^i(m)の値についてそれぞれ計算して置けばよい。ρの尻尾の部分で終わる場合もあるので小さいところでは真面目に計算するようにする。
テストケースが多いらしくTLEするので多少定数倍を改善すれば通る。

acceptされたコード

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

const int64 INF = (1LL<<62) - 2; 

//phi(n)を返す。計算量O(sqrt(n))
int64 eulerPhi(int64 x){
	int64 ret = x;
	for(int64 i = 2; i*i <=  x; i++) if (x%i == 0) {
		ret = ret / i * (i - 1);
		for ( ; x%i == 0; x/=i);
	}
	if (x != 1) {
		ret = ret / x * (x - 1);
	}
	return ret;
}

int64 calcPow(int64 x, int64 n, int64 mod) {
	int64 ret = 1;
	for (; n; n >>= 1, x = x * x % mod) if (n&1) {
		ret = ret * x % mod;
	}
	return ret;
}


const int MAX_B = 100;

int N, B, I;
vector<int> loops;
int64 pows[MAX_B + 1][MAX_B + 1][70];

int64 subPow(int64 x, int n, int id) {
	int64 ret = 1;
	for (; n; n &= n-1) {
		int l = __builtin_ctz(n);
		ret = ret * pows[x][id][l] % loops[id];
	}

	return ret;
}

bool init() {
	return scanf("%d%d%d", &B, &I, &N) == 3;
}

void solve() {
	char format[] = "%00d\n";
	format[2] = char(N + '0');
	if (B == 1) {
		printf(format, 1);
		return ;
	}
	int ten = calcPow(10, N, INF);

	int64 x = 1, actual = 1;
	for (int i = 0; i < I; ++i) {
		int L = loops[I - 1 - i];
		if (actual < INF) {
			x = subPow(B, actual, I - 1 - i);
			if (log(B) * actual < 9) {
				actual = calcPow(B, actual, INF);
			}
			else {
				actual = INF;
			}
		}
		else {
			x = subPow(B, x + L, I - 1 - i);
		}
	}

	printf(format, x % ten);
}

void prepare() {
	loops.push_back(10000000);
	for (; (int)loops.size() < MAX_B; loops.push_back(eulerPhi(loops.back()))) ;

	for (int i = 2; i <= MAX_B; ++i) {
		for (int j = 0; j < MAX_B; ++j) {
			pows[i][j][0] = i;
			for (int k = 0; k < 65; ++k) {
				pows[i][j][k+1] = pows[i][j][k] * pows[i][j][k] % loops[j];
			}
		}
	}
}

int main() {
	prepare();
	for (;init();) {
		solve();
	}
	return 0;
}