洛谷 [P2480] 古代猪文

卢卡斯定理

注意特判底数和模数相等的情况

http://www.cnblogs.com/poorpool/p/8532809.html
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define ll long long

using namespace std;

const int MOD = 999911659;

ll n, g, p[5] = {0, 2, 3, 4679, 35617}, ans[5], fac[100000], ni[100000];

ll exgcd(ll a, ll b, ll & x, ll & y ){

	if(!b) {

		x = 1; y = 0;

		return a;

	}

	ll t = exgcd(b, a % b, y, x);

	y -= a / b * x;

	return t;

}

ll getni(ll x, ll p) {

	ll a, b;

	exgcd(x, p, a, b);

	(a += p) %= p;

	return a;

}

ll lucas(ll a, ll b, ll p) {

	if(a < b) return 0;

	if(a < p) return fac[a] * ni[b] * ni[a - b] % p;

	else return lucas(a % p, b % p, p) * lucas(a / p, b / p, p) % p;

}

void work(int x) {

	memset(fac, 0, sizeof(fac));

	memset(ni, 0, sizeof(ni));

	fac[1] = fac[0] = ni[0] = ni[1] = 1;

	for(int i = 2; i < p[x]; i++) fac[i] = fac[i - 1] * i % p[x];

	for(int i = 2; i < p[x]; i++) ni[i] = (p[x] - p[x] / i) * ni[p[x] % i] % p[x];

	for(int i = 2; i < p[x]; i++) (ni[i] *= ni[i - 1]) %= p[x];

	ll i = 1ll;

	for( ; i * i < n; i++) {

		if(n % i == 0) {

			ans[x] += lucas(n, i, p[x]);

			//cout << ans[x] << endl;

			ans[x] += lucas(n, n / i, p[x]);

			//cout << ans[x] << endl;

			ans[x] %= p[x];

			//cout << ans[x] << endl;

		}

	}

	if(i * i == n) ans[x] += lucas(n, i, p[x]);

	//cout << ans[x] << endl;

	//cout << endl;

	ans[x] %= p[x];

}

ll CRT() {

	ll M = MOD - 1;

	ll rt = 0ll;

	for(int i = 1; i <= 4; i++) {

		rt += ans[i] * getni(M / p[i], p[i]) * (M / p[i]) % M;

	}

	//cout << rt << endl;

	return rt % M;

}

ll quick_mod(ll a, ll k) {

	ll ans = 1ll;

	while(k) {

		if(k & 1ll) (ans *= a) %= MOD;

		(a *= a) %= MOD;

		k >>= 1;

	}

	return ans;

}

int main() {

	cin >> n >> g;

	if(g == MOD) {printf("0\n");return 0;}

	for(int i = 1; i <= 4; i++) {

		work(i);

		//cout << ans[i] << endl;

	}

	cout << quick_mod(g, CRT()) << endl;

	return 0;

}
巴特西

洛谷 [P2480] 古代猪文

卢卡斯定理

最新文章

热门文章
