BZOJ 1951 古代猪文

发表于 | 更新于

Link

Solution

求 首先，根据费马小定理，当pp为质数，gcd(a,p)==1gcd(a,p)==1时， 这个模数是质数，很好！ 当 时，G==999911659G==999911659，答案为00，需要特判掉。 否则，只要求出∑k∣NCNK999911658\sum_{k|N}C_N^K 999911658问题就解决了。 注意到999911658999911658不是个质数，但它的分解是四个一次的质数相乘，可以直接用Lucas定理，再用CRT合并。

Tips

不管是做数学题还是做OI题，在分析的时候需要有严谨的思维，各个定理的适用条件一定要熟知。 数论题能打表的范围内如果可以的话一定要打表，优化的效果不是盖的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}

typedef long long LL;
int Pow(int base,int v,int P)
{
	int res=1;
	while(v)
	{
		if(v&1)
			res=(LL)res*base%P;
		base=(LL)base*base%P;
		v>>=1;
	}
	return res;
}
void exgcd(int a,int b,LL &x,LL &y)
{
	if(!b){x=1,y=0;}
	else
	{
		exgcd(b,a%b,x,y);
		LL nx=y,ny=x-(a/b)*y;
		x=nx,y=ny;
	}
}
int inv(int a,int n)
{
	LL x,y;
	exgcd(a,n,x,y);
	((x%=n)+=n)%=n;
	return x;
}

namespace iLucas
{
	const int dv[]={0,2,3,4679,35617},dc=4,tM[]={0,499955829,333303886,289138806,877424796};
	const int MODU=999911658,SIZE=1e5;
	int table[5][SIZE];
	void Init()
	{
		for(int i=1,*fac;i<=dc;i++)
		{
			fac=table[i];fac[0]=1;
			for(int j=1;j<=dv[i];j++)
				fac[j]=(LL)fac[j-1]*j%dv[i];
		}
	}
	int __C(int n,int m,int idx)
	{
		if(n<m) return 0;
		static int P,*fac;
		P=dv[idx],fac=table[idx];
		return (LL)fac[n]*inv(fac[m],P)%P*inv(fac[n-m],P)%P;
	}
	int Lucas(int n,int m,int idx)
	{
		int res=1,P=dv[idx];
		while(n && m)
		{
			res=(LL)res*__C(n%P,m%P,idx)%P;
			n/=P,m/=P;
		}
		return res;
	}
	int A[5];
	int CRT()
	{
		int res=0;
		for(int i=1;i<=dc;i++) 
			res=((LL)A[i]*tM[i]%MODU+res)%MODU;
		return res;
	}
	int C(int n,int m)
	{
		
		for(int i=1;i<=dc;i++) A[i]=Lucas(n,m,i);
		return CRT();
	}
}
int C(int n,int m)
{
	if(n<m) return 0;
	return iLucas::C(n,m);
	
}
int Calc(int n)
{
	const int P=999911658;
	int res=0;
	for(int i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			res=((LL)res+C(n,i))%P;
		if(i*i!=n)
			res=((LL)res+C(n,n/i))%P;
		}
	}
	return res;
}
int main()
{
	const int MODU=999911659;
	iLucas::Init();
	int n,G;get(n),get(G);
	if(G==MODU) puts("0");
	else printf("%d\n",Pow(G,Calc(n),MODU));
	return 0;
}
/* AC Record(Bugs) *
 * TLE fac table
 * WA if i*i!=n!!!
 * WA if n==G!!!
 * * * * * * * * * */