P2480 [SDOI2010]古代猪文
声明：本博客所有题解都参照了网络资料或其他博客，仅为博主想加深理解而写，如有疑问欢迎与博主讨论✧｡٩(ˊᗜˋ)و✧*｡
题目描述
猪王国的文明源远流长，博大精深。
\(iPig\) 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为 \(n\)。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。
\(iPig\) 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰为远古时期的 \(1/k\) ，其中 \(k\) 是 \(n\) 的一个正约数（可以是 \(1\) 或 \(n\)）。不过具体是哪 \(1/k\)，以及 \(k\) 是多少，由于历史过于久远，已经无从考证了。
\(iPig\) 觉得只要符合文献，每一种 \(k|n\) 都是有可能的。他打算考虑到所有可能的 \(k\)。显然当 \(k\) 等于某个定值时，该朝的猪文文字个数为 \(n/k\)。然而从 \(n\) 个文字中保留下 \(n/k\) 个的情况也是相当多的。\(iPig\) 预计，如果所有可能的 \(k\) 的所有情况数加起来为 \(p\) 的话，那么他研究古代文字的代价将会是 \(g^p\) 。
现在他想知道猪王国研究古代文字的代价是多少。由于 \(iPig\) 觉得这个数字可能是天文数字，所以你只需要告诉他答案除以 \(999911659\) 的余数就可以了。
输入格式
一行两个正整数 \(n,g\)。
输出格式
输出一行一个整数表示答案。
\(Solution\)
看题解大佬们都好不屑啊…几个式子一摆就没了…我自己理解还要好一会，果然太菜了
首先，由于要从 \(n\) 中选出 \(\dfrac{n}{k}\) 个，又因为 \(\dfrac{n}{k} | n\) ，所以 \(p\) 就等于 \(\sum{k|n} \ C_{n}^{k}\)
又因为 \(999911659\) 是个质数，根据欧拉定理得，\(g^p \equiv g^{p \% 999911658} \pmod{p}\)
接下来就求 \(p \ \% \ 999911658\)
发现是大组合数，可以用 \(lucas\) 定理，但是模数太大（ \(lucas\) 定理时间复杂度为 \(O(p\log_pn)\)），显然过不去
但是我们可以发现， \(999911658\) 可以质因数分解为 \(2 * 3 * 4679 * 35617\)，于是我们可以先求得在这模四个数下的 \(p\) ，然后用中国剩余定理最后求解
完结撒花✿✿ヽ(°▽°)ノ✿
\(Code\)
#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++i)
using namespace std;
ll read();
const int N = 36000 + 5;
ll n, g;
ll a[4], b[4] = {2, 3, 4679, 35617}, kk = 999911658;
ll mul[N], f[N], ans;
void init(ll mod)
{
f[0] = 1;
F(i, 1, mod) f[i] = f[i - 1] * i % mod;
}
ll qpower(ll x, ll y, ll mod)
{
ll res = 1;
while(y)
{
if(y & 1) res = res * x % mod;
x = x * x % mod, y >>= 1;
}
return res;
}
ll C(ll n, ll m, ll mod)
{
if(n < m) return 0;
return f[n] * qpower(f[m], mod - 2, mod) % mod * qpower(f[n - m], mod - 2, mod) % mod;
}
ll lucas(ll n, ll m, ll mod)
{
if(n < m) return 0;
if(! n) return 1;
return lucas(n / mod, m / mod, mod) * C(n % mod, m % mod, mod) % mod;
}
int main()
{
n = read(), g = read();
if(g % (kk + 1) == 0)
{
puts("0");
return 0;
}
F(s, 0, 3)
{
init(b[s]);
F(i, 1, sqrt(n))
if(n % i == 0)
{
a[s] = (a[s] + lucas(n, i, b[s])) % b[s];
if(i * i != n) a[s] = (a[s] + lucas(n, n / i, b[s])) % b[s];
}
}
F(i, 0, 3) ans = (ans + a[i] * (kk / b[i]) % kk * qpower(kk / b[i], b[i] - 2, b[i])) % kk;
printf("%lld", qpower(g, ans, kk + 1));
return 0;
}
ll read()
{
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
