[bzoj 1951] [Sdoi2010]古代猪文

求. (1≤n,g≤10^9) 欧拉定理的推论: 若, 则.

卢卡斯定理: 若是质数, 则.

999911659是一个质数, 仍然很大. 做一下质因数分解: . 是一个square-free number, 质因子不多, 而且每个质因子都不大, 正好可以用卢卡斯定理算出每个模的答案, 再用中国剩余定理合并. 找的因子枚举即可. 这样, 把取模后的指数求出来, 再跑一个快速幂就行了.

注意欧拉定理的条件, 底数需要和模数互质. 由于这里的模是质数, 数据范围内只需特判的情况, 输出0. 出题人比较细心, 看到Po姐的博客里说, 有一组数据 n=999911657, G=999911659 来卡这一点.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef long long ll;
const int mod[] = {2, 3, 4679, 35617}, M = 35617, P = 999911659, Q = P-1;
ll fac[4][M], inv[4][M], ans[4];

ll fpm(ll x, ll n, ll m)
{
	ll y = 1;
	for (; n; n >>= 1, (x *= x) %= m)
		if (n & 1)
			(y *= x) %= m;
	return y;
}

inline ll inverse(ll x, ll p)
{
	return fpm(x, p-2, p);
}

void init()
{
	Rep (i, 0, 4) {
		fac[i][0] = inv[i][0] = 1;
		Rep (j, 1, mod[i])
			fac[i][j] = fac[i][j-1] * j % mod[i];
		inv[i][mod[i]-1] = inverse(fac[i][mod[i]-1], mod[i]);
		Down (j, mod[i]-2, 1)
			inv[i][j] = inv[i][j+1] * (j+1) % mod[i];
	}
}

ll C(ll n, ll k, int i, ll p)
{
	if (!n && !k) return 1;
	ll a = n % p, b = k % p;
	return b > a ? 0 : fac[i][a] * inv[i][b] % p * inv[i][a-b] % p * C(n/p, k/p, i, p) % p;
}

int n;

inline void add(int i)
{
	Rep (j, 0, 4) {
		ll m = mod[j];
		ans[j] += C(n, i, j, m);
		ans[j] -= ans[j] >= m ? m : 0;
	}
}

int main()
{
	init();
	int g;
	scanf("%d%d", &n, &g);
	if (g == P) return puts("0"), 0;
	for (int i = 1; i*i <= n; ++i)
		if (n % i == 0) {
			add(i);
			if (i*i != n)
				add(n/i);
		}
	ll e = 0;
	Rep (i, 0, 4) {
		e += ans[i] * Q/mod[i] % Q * inverse(Q/mod[i], mod[i]) % Q;
		e -= e >= Q ? Q : 0;
	}
	printf("%lld\n", fpm(g, e, P));
	return 0;
}