POJ 1150: The Last Non-zero Digit

http://poj.org/submit?problem_id=1150

初中国剰余定理かもしれない。
(X/10^k)mod10を求めればいいです。ここでkはXが10で割り切れる回数です。
中国剰余定理より
(X/10^k)mod10 <=> (X/10^k)mod2, (X/10^k)mod5となります。
対称性よりmod5についてのみ注目して考えましょう。
X=a*5^eとします。ここでa mod5 != 0です。a mod5とeは蟻本の方法で求められます。するとe>=kが成立するのは明らかです。
e>kのとき、(X/10^k)mod5 = 0です。
e=kのとき、(X/10^k)≡(X/5^k)*(1/2^k)≡a*inv[2^k](mod5)となるので求められます。

int fact[6][11];
int inv[6][11];

ll mod_pow(ll a, ll n, ll mod) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2, mod);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}


int mod_fact(int n, int p, int &e) {
	e = 0;
	if(n == 0) return 1;
	int res = mod_fact(n / p, p, e);
	e += n / p;

	if((n / p) % 2 != 0) return res * (p - fact[p][n % p]) % p;
	else return res * fact[p][n % p] % p;
}

int N, M;
int ans[5][10];

int main() {
	fact[2][0] = fact[2][1] = 1;
	inv[2][1] = 1;
	fact[5][0] = fact[5][1] = 1;
	inv[5][1] = 1;
	rep(i, 2, 5) {
		fact[5][i] = fact[5][i - 1] * i % 5;
		inv[5][i] = 5 - inv[5][5 % i] * (5 / i) % 5;
	}
	rep(i, 0, 10) {
		ans[i % 2][i % 5] = i;
	}
	while(scanf("%d%d", &N, &M) != EOF) {
		int e2_1, e2_2;
		int e5_1, e5_2;
		int a2_1 = mod_fact(N, 2, e2_1);
		int a2_2 = mod_fact(N - M, 2, e2_2);
		int a5_1 = mod_fact(N, 5, e5_1);
		int a5_2 = mod_fact(N - M, 5, e5_2);
		int a2 = a2_1 * inv[2][a2_2] % 5;
		int a5 = a5_1 * inv[5][a5_2] % 5;
		int e2 = e2_1 - e2_2;
		int e5 = e5_1 - e5_2;
		if(e2 > e5) {
			a5 = a5 * inv[5][mod_pow(2, e5, 5) % 5] % 5;
			printf("%d\n", ans[0][a5]);
		}
		else if(e2 == e5) {
			a5 = a5 * inv[5][mod_pow(2, e5, 5) % 5] % 5;
			a2 = a2 * inv[2][mod_pow(5, e2, 2) % 2] % 2;
			printf("%d\n", ans[a2][a5]);
		}
		else {
			a2 = a2 * inv[2][mod_pow(5, e2, 2) % 2] % 2;
			printf("%d\n", ans[a2][0]);
		}
	}
}