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]); } } }