題目鏈接

solution

理解完題意，發現就是求$g^{\sum\limits_{k|n}C_n^k}$，

利用歐拉降冪，可以將式子寫成$g^{\sum\limits_{k|n}C_n^k%\phi(mod)}$

只要想辦法把指數求出來就行了，

看一下資料范圍，發現$n$比較大，不能直接計算組合數，然后考慮用$lucas$，但是模數也比較大，

因為模數不是質數，對其進行質因數分解得到$2,3,4679,35671$，發現這四個質數都是可以進行$lucas$的，所以思路就很明顯了，先將模數分解質因子，然后分別求出答案，得到四個形如$\sum\limits_{k|n}C_n^{k\equiv a_i(mod\ m_i)$的式子，然后用$CRT$將其合并起來，得到$\sum\limits_{k|n}C_n}k%\phi(mod)$

PS:因為歐拉降冪必須滿足底數與模數互質，因為題目所給模數為質數，所以當$g$為所給模數倍數時不能使用歐拉降冪，而此時答案顯然為$0$，需要特判，

code

/*
* @Author: wxyww
* @Date:   2020-04-22 09:31:36
* @Last Modified time: 2020-04-22 09:52:12
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100010;
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;
}

ll qm(ll x,ll y,ll mod) {
	ll ret = 1;
	for(;y;y >>= 1,x = x * x % mod)
		if(y & 1) ret = ret * x % mod;
	return ret;
}
int jc[N],inv[N];

ll C(int n,int m,int mod) {
	if(n < m) return 0;
	if(n < mod) return jc[n] * inv[m] % mod * inv[n - m] % mod;
	return C(n % mod,m % mod,mod) * C(n / mod,m / mod,mod) % mod;
}
ll a[5];
ll b[5] = {0,2,3,4679,35617};
ll solve(int n,int mod) {
	jc[0] = 1;
	for(int i = 1;i < mod;++i) jc[i] = jc[i - 1] * i % mod;
	inv[mod - 1] = qm(jc[mod - 1],mod - 2,mod);

	// cout<<inv[mod - 1]<<endl;

	for(int i = mod - 2;i >= 0;--i) inv[i] = inv[i + 1] * (i + 1) % mod;

	ll ret = 0;

	for(int i = 1;i * i <= n;++i) {
		if(n % i) continue;
		ret += C(n,i,mod);
		ret %= mod;
		if(i * i != n) ret += C(n,n / i,mod),ret %= mod;
		// if(mod == 2) {
			// printf("!!%d\n",C(n,i,mod));
		// }
	}

	return ret;
}
int main() {
	int n = read(),G = read();
	if(G % 999911659 == 0) {
		puts("0");return 0;
	}
	for(int i = 1;i <= 4;++i) {
		a[i] = solve(n,b[i]);
		// printf("%d\n",a[i]);
	}
	ll M = 999911658;
	ll ans = 0;
	for(int i = 1;i <= 4;++i) {
		ans += a[i] * (M / b[i]) % M * qm(M / b[i],b[i] - 2,b[i]) % M;
		ans %= M;
	}
	cout<<qm(G,ans,M + 1);
	return 0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57177.html

標籤：其他

上一篇：C# WPF從RIOT API獲取資料(RIOT代表作品《英雄聯盟》)

下一篇：資料結構（C語言版）---佇列

bzoj1951 [SDOI2010]古代豬文

solution

code