网站建设公司怎么运营,网站服务器哪里的好,济南建设工程信息网站,怎么做网站转盘P2480 [SDOI2010]古代猪文
题意#xff1a;
给你n和g#xff0c;求g∑d∣nCndmodpg^{\sum_{d|n}C_{n}^{d}}\bmod pg∑d∣nCndmodp p999911659
题解#xff1a;
这个一个综合性很强的数论题 涉及到欧拉定理#xff0c;Lucas定理#xff0c;中国剩余定理#xff0c…P2480 [SDOI2010]古代猪文
题意
给你n和g求g∑d∣nCndmodpg^{\sum_{d|n}C_{n}^{d}}\bmod pg∑d∣nCndmodp p999911659
题解
这个一个综合性很强的数论题 涉及到欧拉定理Lucas定理中国剩余定理挺好的一个题 首先根据欧拉定理推论 若正整数an互质对于任意的正整数b有ab≡abmodϕ(n)(modn)a^b \equiv a^{b\bmod \phi(n)}(\bmod n)ab≡abmodϕ(n)(modn) 所以 g∑d∣nCndmodϕ(p)modpg^{\sum_{d|n}C_{n}^{d}\bmod \phi(p)}\bmod pg∑d∣nCndmodϕ(p)modp ϕ(p)p−1999911658\phi(p)p-1999911658ϕ(p)p−1999911658 g∑d∣nCndmod999911658modpg^{\sum_{d|n}C_{n}^{d}\bmod 999911658}\bmod pg∑d∣nCndmod999911658modp 现在的关键在于求∑d∣nCndmod999911658\sum_{d|n}C_{n}^{d}\bmod 999911658∑d∣nCndmod999911658, 999911658不是质数咋搞那我们可以将其质因子分解9999116584679 * 3 * 2 *35617每个质因子的次数都是1所以我们只需要用CRT来求解如下的方程组 求出p后最后再一个快速幂输出答案
CRT
inline ll CRT()
{ll ans0;for(register int i1;icnt;i){ll Mmod/p[i],tqpow(M,p[i]-2,p[i]);ans(ansa[i]%mod*t%mod*M%mod)%mod;}return (ansmod)%mod;
}Lucas组合数
ll C(int a, int b, ll mod)
{if (b a)return 0;return fac[a] % mod * inv[b] % mod * inv[a - b] % mod;
}
ll Lucas(ll n, ll m, ll p)
{if (m 0)return 1;return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}递推求阶乘逆元
(n−1)!×n[n!]−1≡1modp(n−1)!×n[n!]^{−1}≡1 \bmod p(n−1)!×n[n!]−1≡1modp
void init() {fact[0] 1;for (int i 1; i maxn; i) {fact[i] fact[i - 1] * i %mod;}inv[maxn - 1] power(fact[maxn - 1], mod - 2);for (int i maxn - 2; i 0; i--) {inv[i] inv[i 1] * (i 1) %mod;}
}
代码
but代码存在问题还没修改出哪里错了
目前95分错了第一个点人傻了
// Problem: P2480 [SDOI2010]古代猪文
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2480
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Data:2021-08-26 15:50:36
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 4e4 9;
ll n, g;
ll fac[maxn];
ll inv[maxn];
const int mod 999911659;
ll p[maxn];
ll c[maxn];
ll a[maxn];
int cnt 0;
int tot 0;
ll poww(ll a, ll b, ll mod)
{ll ans 1;while (b) {if (b 1)ans ans * a % mod;a a * a % mod;b 1;}return ans % mod;
}
ll exgcd(int a, int b, ll x, ll y)
{if (b 0) {x 1;y 0;return a;}int gcd exgcd(b, a % b, x, y);ll t x;x y;y t - a / b * y;return gcd;
}
ll CRT(int k, ll a[], ll r[], ll mod)
{ll n 1, ans 0;ll x,y;for (int i 1; i k; i)n n * r[i];for (int i 1; i k; i) {ll m n / r[i];exgcd(m, r[i], x, y);ans (ans a[i] % mod * m % mod * x % mod) % mod;}return (ans % mod mod) % mod;
}
ll C(int a, int b, ll mod)
{if (b a)return 0;return fac[a] % mod * inv[b] % mod * inv[a - b] % mod;
}
ll Lucas(ll n, ll m, ll p)
{if (m 0)return 1;return Lucas(n / p, m / p, p) * C(n % p, m % p, p) % p;
}
void init(int p)
{fac[0] 1;for (int i 1; i p; i) {fac[i] fac[i - 1] * i % p;}inv[p]0;inv[p-1]poww(fac[p-1],p-2,p);for(register int ip-2;i0;i--)inv[i]inv[i1]*(i1)%p;
}
void calc(int x)
{init(p[x]);for (int i 1; i tot; i) {a[x] (a[x] Lucas(n, c[i], p[x])) % p[x];}
}int main()
{//rd_test();cin n g;if (g % mod 0) {printf(0--\n);return 0;}ll phi mod - 1;for (int i 2; i * i (mod - 1); i) { //对mod-1进行质因子分解if (phi % i 0) {p[cnt] i;while (phi % i 0)phi phi / i;}}if (phi ! 1)p[cnt] phi;for (int i 1; i * i n; i) { //c存的是n的因子if (n % i 0) {c[tot] i;if (i * i ! n)c[tot] n / i;}}for (int i 1; i cnt; i)calc(i); //预初理出组合数情况ll sum CRT(cnt, a, p, mod - 1)%mod;printf(%lld\n, poww(g, sum, mod) % mod);//Time_test();
}
AC代码
#include iostream
#include cstdio
#include algorithm
#include cstring
#include cmath
using namespace std;
#define Mod 999911659
#define mod 999911658
#define maxn 40005
typedef long long ll;
ll n,g;
ll d[maxn],tot;
ll p[10],cnt;inline ll qpow(ll a,ll k,ll p)
{ll res1;while(k){if(k1) res(res*a)%p;a(a*a)%p;k1;}return res%p;
}ll fac[maxn],inv[maxn];
inline void init(ll p)
{fac[0]1;for(register int i1;ip;i)fac[i]fac[i-1]*i%p;inv[p]0;inv[p-1]qpow(fac[p-1],p-2,p);for(register int ip-2;i0;i--)inv[i]inv[i1]*(i1)%p;
}inline ll C(ll n,ll m,ll p)
{if(mn) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;
}inline ll Lucas(ll n,ll m,ll p)
{if(m0) return 1;return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}ll a[10];
inline void calc(int x)
{init(p[x]);for(register int i1;itot;i)a[x](a[x]Lucas(n,d[i],p[x]))%p[x];
}inline ll CRT()
{ll ans0;for(register int i1;icnt;i){ll Mmod/p[i],tqpow(M,p[i]-2,p[i]);ans(ansa[i]%mod*t%mod*M%mod)%mod;}return (ansmod)%mod;
}int main()
{scanf(%lld%lld,n,g);if(g%Mod0){printf(0\n);return 0;}ll tmod;for(register int i2;i*imod;i){if(t%i0){p[cnt]i;while(t%i0) tt/i;}}if(t!1) p[cnt]t;for(register int i1;i*in;i){if(n%i0){d[tot]i;if(i*i!n) d[tot]n/i;}}for(register int i1;icnt;i) calc(i);printf(%lld,qpow(g,CRT(),Mod));return 0;
}
