洛谷 2480 bzoj 1951 [SDOI2010]古代猪文 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1.1k 字 | 阅读时长 ≈ 5 分钟

这题是个毒瘤题。你基本上要把你知道的数论算法都写上才能过。

题意简述

求，其中。（看不清的话右键公式，点击）

思路

用扩展：定理暴力求上面的，枚举因数是根号的，是带log的，所以能过。然后无哦们用欧拉降幂对质数取膜。取膜完发现这还不是个质数，所以要用中国剩余定理合并答案。

具体思路

step.1 假设我们能算上面那个

我们发现那个膜数是个质数。那么它的值就是。

然后我们把它分解，它。我们只要以这四个数作为膜数，分别求出答案，然后用中国剩余定理合并一下即珂。就相当于求出四个答案，然后解方程：

这个方程很容易解。珂是如何求上面那个呢？

step.2 上面那个

枚举的话是，但是我们还要快速的求组合数。考虑扩展卢卡斯定理：

。然后对于后面那个，我们只要预处理出$1,p$之间阶乘和阶乘的逆元即珂。然后这个预处理不是每次都要预处理的，每次算之前预处理一下即珂。复杂度之和是，珂以忽略不计。然后这样递归求的话，大概总的复杂度是。是能过的。

好了，就到这里了，很短。但是要写很多东西。

step.3 快速幂 略

实现细节

  1. 特判的情况，输出（要不然你就会到自闭）

代码：

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
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define P 44444
	#define mod 999911658
	#define int long long 
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	int n,g;
	void R1(int &x)
	{
	    x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    x=(f==1)?x:-x;
	}
	void Input()
	{
		R1(n),R1(g);
	}

	int fac[P],ifac[P];//预处理阶乘和阶乘的逆元
	int qpow(int a,int b,int m)//快速幂
	{
		int r=1;
		while(b)
		{
			if (b&1) r=r*a%m;
			a=a*a%m,b>>=1;
		}
		return r;
	}
	int C1(int n,int k,int p)//求一个组合数
	{
		if (n<k) return 0;
		if (k==0 or k==n or n==0) return 1; 

		return fac[n]*ifac[k]%p*ifac[n-k]%p;
                //仅限n,k<=p的情况，要不然有一个是0就除爆了
	}
	int C(int n,int k,int p)
	{
		if (n<k) return 0;
		if (k==0 or k==n or n==0) return 1; 

		return C(n/p,k/p,p)*C1(n%p,k%p,p)%p;//Lucas定理
	}
	int calc(int n,int p)
	{
		fac[0]=1;
		F(i,1,p) fac[i]=fac[i-1]*i%p;
		ifac[p-1]=qpow(fac[p-1],p-2,p);
		D(i,p-2,1) ifac[i]=ifac[i+1]*(i+1)%p;//预处理

		int ans=0;
		for(int i=1;i*i<=n;++i)//枚举因数
		{
			if (n%i==0)
			{
				int a=i;
				ans+=C(n,a,p);//暴力计算
				ans%=p;
				if (i*i!=n)//别忘了判这个
				{
					int b=n/i;
					ans+=C(n,b,p);//暴力计算
					ans%=p;
				}
			}
		}
		return ans;
	}
	int a[5],b[5];
	int CRT()
	{
		int ans=0;
		F(i,1,4)
		{
			ans=(ans+a[i]*(mod/b[i])%mod*qpow(mod/b[i],b[i]-2,b[i]))%mod;
		}
		return ans;//扩展中国剩余定理
	}
	void Soviet()
	{
		if (g%(mod+1)==0)//会导致你WA掉的特判
		{
			puts("0");
			return;
		}
		b[1]=2,b[2]=3,b[3]=4679,b[4]=35617;//四个膜数
		F(i,1,4)
		{
			a[i]=calc(n,b[i]);//算出四个答案
		}
		printf("%lld\n",qpow(g,CRT(),mod+1)%(mod+1));
                //别忘了最后输出g^CRT，而且膜数是mod+1,我令mod=
	}
	void IsMyWife()
	{
		Input();
		Soviet();
	}
	#undef int //long long 
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}

w