P2480 [SDOI2010] 古代猪文

简单数学题。

显然答案是 \(g^{\sum_{d|n}C_n^d}\)。

考虑到 \(mod\) 是质数，所以 \(g^{mod-1}\equiv 1\pmod {mod}\)，那么考虑算出指数模上 \(mod - 1\)。

注意到 \(mod - 1\) 并不是质数，显然可以质因数分解后 CRT 合并。

于是就做完了。

Code

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cassert>
#include <chrono>
#include <random>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define desktop "C:\\Users\\MPC\\Desktop\\"
#define IOS ios :: sync_with_stdio (false),cin.tie (0),cout.tie (0)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> PII;
const int dx[] = {1,0,-1,0},dy[] = {0,-1,0,1};
template <typename T1,typename T2> bool tomax (T1 &x,T2 y) {
    if (y > x) return x = y,true;
    return false;
}
template <typename T1,typename T2> bool tomin (T1 &x,T2 y) {
    if (y < x) return x = y,true;
    return false;
}
LL power (LL a,LL b,LL p) {
    LL ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int fastio = (IOS,0);
#define endl '\n'
#define puts(s) cout << s << endl
const int N = 50010,MOD = 999911658;
LL fact[N];
LL m[4] = {2,3,4679,35617};
LL a[4];
LL n,g;
void init (int p) {
	fact[0] = 1;
	for (int i = 1;i <= p;i++) fact[i] = fact[i - 1] * i % p;
}
LL C (int n,int m,int p) {
	if (n < m) return 0;
	return fact[n] * power (fact[m],p - 2,p) % p * power (fact[n - m],p - 2,p) % p;
}
LL lucas (int n,int m,int p) {
	if (n < m) return 0;
	if (!n) return 1;
	return lucas (n / p,m / p,p) * C (n % p,m % p,p) % p;
}
LL CRT () {
	LL ans = 0;
	for (int i = 0;i < 4;i++) ans = (ans + a[i] * (MOD / m[i]) % MOD * power (MOD / m[i],m[i] - 2,m[i])) % MOD;
	return ans;
}
int main () {
	cin >> n >> g;
	if (g % (MOD + 1) == 0) {
		puts ("0");
		return 0;
	}
	for (int k = 0;k < 4;k++) {
		init (m[k]);
		for (int i = 1;i <= n / i;i++) {
			if (n % i) continue;
			a[k] = (a[k] + lucas (n,i,m[k])) % m[k];
			if (n / i != i) a[k] = (a[k] + lucas (n,n / i,m[k])) % m[k];
		}
	}
	// cout << CRT () << endl;
	cout << power (g,CRT (),MOD + 1) << endl;;
	return 0;
}