话说 [SDOI2010] 为啥题目里都带了猪，还包括那个臭名昭著的猪国杀。
题目传送门
题目难度：
这个题目太长了，我的盟友 tangtianyao0123 告诉我其实是求这个式子的值：
\[g^{\sum_{i\mid n} C_n^i}\bmod999911659
\]
我们写一个质数判断知道 \(999911659\) 是质数，由欧拉定理
\[a^b\bmod p=a^{b\bmod p-1}\bmod p
\]
那么我们其实只要求
\[g^{\sum_{i\mid n} C_n^i \bmod 999911658}\bmod999911659
\]
加上结合律：
\[g^{\sum_{i\mid n} (C_n^i \bmod 999911658)}\bmod999911659
\]
经过我们不为人知的方式，我们知道 \(999911658\) 是可以分解成 \(2\times3\times4679\times35617\) 的，运用一下 Lucas 定理，和 重庆轨道交通 \(^1\) 中国剩余定理 CRT 的小枚举求法即可。
code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <climits>
#define I using
#define AK namespace
#define IOI std
#define A return
#define C 0
#define int long long
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
I AK IOI;using ll = long long;
using ull = unsigned long long;
using lb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;constexpr int mod = 999911658;
constexpr int maxn = 35620;int n, g, ans;int jc[maxn], c[4] = {2, 3, 4679, 35617}, d[4];int binpow(int a, int b, int m){int res = 1;while (b){if (b & 1)res = (res * a) % m;a = (a * a) % m;b >>= 1;}return res;
}//快速幂int calC(int n, int m, int p){if (n < m)A C;A jc[n] % p * binpow(jc[m], p - 2, p) % p * binpow(jc[n - m], p - 2, p) % p;//用组合数公式计算组合数
}int Lucas(int n, int m, int p){if (!m)A 1;A Lucas(n / p, m / p, p) % p * calC(n % p, m % p, p) % p;//用 Lucas 定理
}int CRT(){int p = 1, ans = C;for (int i = 0; i < 4; i++){while (ans % c[i] != d[i])ans += p;p = p / __gcd(p, c[i]) * c[i];}return ans;
}//枚举求 CRTvoid init(){jc[0] = 1;for (int i = 1; i <= maxn - 3; i++)jc[i] = jc[i - 1] * i % mod;
}//阶乘数组初始化signed main() {fast;freopen("std.in", "r", stdin);freopen("std.out", "w", stdout);init();cin >> n >> g;for (int i = 1; i * i <= n; i++){if (n % i)continue;//求和要求d[0] = Lucas(n, i, 2);d[1] = Lucas(n, i, 3);d[2] = Lucas(n, i, 4679);d[3] = Lucas(n, i, 35617);ans = (ans + CRT()) % mod;if (n / i != i){d[0] = Lucas(n, n / i, 2);d[1] = Lucas(n, n / i, 3);d[2] = Lucas(n, n / i, 4679);d[3] = Lucas(n, n / i, 35617);ans = (ans + CRT()) % mod;}}if (g == 999911659) A cout << C, C;//这个不加会**else A cout << binpow(g, ans, 999911659), C;A C;
}