洛谷2480 [SDOI2010]古代猪文

标签：数论，Lucas定理，CRT，快速幂

题目

题目传送门

计算$G^{{\sum }_{i|n}C(n,i)}\%P$

$100\%$的数据中，$1\le G\le 1000000000，1\le N\le 1000000000$

分析

根据费马小定理，指数可以变成

${\sum }_{i|n}C(n,i)\%(P?1)$

然后可以使用Lucas定理快速求组合数，之后用快速幂求出答案

999911659的约数有2,3,4679,35617，分别对这四个约数求组合数，之后使用CRT合并

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
    ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;
}
//******head by yjjr******
#define mod 999911659
const int maxn=4e5+6;
int g,n,m[4],fac[4][maxn];
int t[4]={
    2,3,4679,35617};
inline ll qpow(ll a,ll b,int p){
    ll re=1;while(b){
    if(b&1)re=(ll)(re*a)%p;b>>=1,a=(ll)(a*a)%p;}return re;
}
inline ll C(int n,int m,int x){
    if(n<m)return 0;return (ll)(1ll*fac[x][n]*qpow(fac[x][n-m]*fac[x][m],t[x]-2,t[x])%t[x]);
}
inline ll Lucas(int n,int m,int x){
    if(m==0)return 1;return (ll)(1ll*C(n%t[x],m%t[x],x)*Lucas(n/t[x],m/t[x],x)%t[x]);
}
void exgcd(int a,int b,int &x,int &y){
    if(b==0){
    x=1,y=0;return;}exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y;
}
inline ll solve(){
    int a1,b1,a2,b2,a,b,c,x,y;a1=t[0],b1=m[0];rep(i,1,3){
    a2=t[i],b2=m[i];a=a1,b=a2,c=b2-b1;exgcd(a,b,x,y);x=((x*c)%b+b)%b;b1=b1+a1*x;a1=a1*b;}return b1;
}
int main(){
    rep(i,0,3){
    fac[i][0]=1;rep(j,1,t[i])fac[i][j]=(fac[i][j-1]*j)%t[i];}n=read(),g=read();if(g==mod){
    puts("0");return 0;}g%=mod;for(int i=1;i*i<=n;i++) if(n%i==0){
    int tmp=n/i;rep(j,0,3){
    if(tmp!=i)m[j]=(m[j]+Lucas(n,i,j))%t[j];m[j]=(m[j]+Lucas(n,tmp,j))%t[j];}}cout<<qpow(g,solve(),mod)<<endl;return 0;
}