题目链接:BZOJ 1951
通过欧拉定理的推论得到组合数部分的模数后,用Lucas定理计算,但是模数不是质数,对模数分解质因数后发现所有质因子的指数都是1,于是用中国剩余定理合并方程.具体思路可见《算法竞赛进阶指南》172页.
调了好久,才发现是快速幂的参数写错了.不多说了,直接上代码吧...心态崩了
code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int p[4] = {2, 3, 4679, 35617};
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y;
y = z - (a / b) * y;
return d;
}
int quickpow(int n, int m, int mod) {
int res = 1;
while (m) {
if (m & 1) res = (ll)res * n % mod;
n = (ll)n * n % mod;
m >>= 1;
}
return res;
}
int jc[4][36000];
int factorial() {
for (int i = 0; i < 4; ++i) {
jc[i][0] = 1;
for (int j = 1; j < p[i]; ++j) {
jc[i][j] = (ll)jc[i][j - 1] * j % p[i];
}
}
}
int inv(int a, int mod) {
int x, y;
exgcd(a, mod, x, y);
return (x % mod + mod) % mod;
}
int lucas(int n, int m, int i) {
if (n < m) return 0;
if (n < p[i] && m < p[i])
return (ll)jc[i][n] * inv(jc[i][n - m] * jc[i][m] % p[i], p[i]) % p[i];
return (ll)lucas(n / p[i], m / p[i], i) * lucas(n % p[i], m % p[i], i) % p[i];
}
int CRT(int n, int a[], int mod) {
int res = 0;
for (int i = 0; i < n; ++i) {
int M = mod / p[i];
int t = inv(M, p[i]);
res = (res + (ll)a[i] * M % mod * t % mod) % mod;
}
return res;
}
int A(int n, int i, int a[]) {
for (int j = 0; j < 4; ++j) {
a[j] += lucas(n, i, j);
}
}
int main() {
int n, g;
cin >> n >> g;
const int mod = 999911658;
if (g == mod + 1) {
cout << 0 << endl;
} else {
factorial();
int a[4];
memset(a, 0, sizeof(a));
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
A(n, i, a);
if (n / i != i) A(n, n / i, a);
}
}
int ans = CRT(4, a, mod);
ans = quickpow(g, ans, mod + 1);
cout << ans << endl;
}
return 0;
}