[SDOI2010]古代猪文

发表于 | 更新于 | 分类于 | 阅读次数：

一个数论没学到1个月的蒟蒻在经过题解的帮助下能A了这道综合性很强的题，感到十分荣幸_(:з」∠)

此题有哪些数论的应用其他题解已经十分完备了，这里我就给大家讲讲做这道题的一些思路以及一些板子在洛谷很少见的一些写法。

  • 题意

推出真正式子的描述就两段

...根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的k分之一，其中k是N的一个正约数（可以是1和N）。...

...他打算考虑到所有可能的k。...。然而从N个文字中保留下N / k个的情况也是相当多的。
...可能的k的所有情况数加起来为P的话，那么他研究古代文字的代价将会是G的P次方。

其中，只要通过K是N的正约数，从N个文字中保留下N / k个的情况也是相当多的以及G的P次方，这三句话就可直接分析出表达式（为了方便，设P=999911659）：
$$G^{\sum \limits_{k|N}*C_N^k}$ $≡ans$ $(mod$ $P)$$

感觉这一步还是挺基础的？毕竟我这种蒟蒻也能看出来_(:з」∠)

推出以上式子后就有点懵逼了：这个G的指数是啥玩意？？那就肯定要在指数上面做文章了。

指数，指数，……，涉及到指数的数论定理好像本蒟蒻只学过欧拉定理了_(:з」∠)

一看模数是指数，就是费马小定理没得跑了！

对于那个模数，列出费马小定理的式子：
$$G^{p-1}$ $≡1$ $(mod$ $P)$$
可见上式每多一个$p-1$，就可以通过下面的式子直接约掉，于是式子就被我们简化成这样：
$$G^{\sum \limits_{k|N}*C_N^k mod P-1}$ $≡ans$ $(mod$ $P)$$
等价于求：
$${\sum \limits_{k|N}*C_N^k}$ $mod$ $(p-1)$$

由于K是N的正约数，可以在$LOG(N)$时间内求出来，那只需要对于任意的K求$C_N^k$ $mod(p-1)$就好了

看来我们已经很接近正解了呢！_(:з」∠)

那我们可以用Lucas
……

……

诶诶诶p-1好像不是质数啊！！卢卡斯是要在质数下才能用的_(:з」∠)

虽说有扩展卢卡斯不要求是素数但是蒟蒻不会啊（会的大佬可以试试_(:з」∠)）

我们在摸了题解后得到了正解：

拆分p-1成4个质数，对于每一个质数求组合数（当然还是LUCAS）列出一个同余方程，在把这些式子联立起来用一个中国剩余定理就可以求出来组合数mod p-1了_(:з」∠)

蒟蒻在得到了这个宝贵的提示后就打出了普通的中国剩余定理（题解里的好像都是扩展剩余定理！？），然后疯狂DEBUG了1小时就过了，思路大概就是这样_(:з」∠)。

其中对于求组合数，民间一直流传着一种O(N)预处理，O(1)查询的做法：

  • 先求出模p意义下的阶乘，逆元以及逆元阶乘（因为求逆元满足积性函数）。
  • 对于任意一个小于p的组合数$C_m^n$，可以直接用$jc[m]*invjc[n]*invjv[m-n]$求出，其中$jc[i]$指到i的阶乘,$invjc[i]$指到i的阶乘逆元，对于LUCAS定理在合适不过了(:з」∠)_

其次求中国剩余定理真的不用像题解里面用扩展的，因为对于4个模数都是p-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
#include <iostream>
#include <cmath>
#include <cstring>
#define ll long long
using namespace std;
const ll p=999911659;
ll pri[6]={999911658,2,3,4679,35617};
ll n,g,k=0,ans=0,x[5],jc[200000][5],ninv[200000][5],inv[200000][50],a,b; 

ll ksm(ll x,ll k,ll p)  //最后算答案，也可以用来求逆元 
{
	ll ans=1;
	while (k)
	{
		if (k%2) ans=ans*x%p;
		k/=2; x=x*x%p;
	}
	return ans%p;
}

void exgcd(int x,int y) //求逆元，其实ksm也可以 
{
    if (!y) 
    {
        a=1; b=0; return;
    }
    exgcd(y,x%y);
    int kk=a; a=b; b=kk-(x/y)*b;
}

ll c(ll n,ll m,int i)
{
	int pp=pri[i];
	if (n==m||n==0) return 1;
	if (n>m||m==0) return 0;
	return jc[m][i]*ninv[n][i]*ninv[m-n][i]%pp; //O(1)查询组合数 
}

ll lucas(ll d,ll n,int i)  //LUCAS 
{
	ll pp=pri[i];
	if (n<pp) return c(d,n,i)%pp;
	else return (lucas(d/pp,n/pp,i)*lucas(d%pp,n%pp,i)%pp);
}

ll find(ll d) //对于每个约数求同余方程及中国剩余定理 
{
	memset(x,0,sizeof(x));
	ll ans=0,div=0;
	for (int i=1;i<=4;i++) x[i]=lucas(d,n,i)%pri[0];
//	for (int i=1;i<=4;i++) cout<<x[i]<<" "; 
	for (int i=1;i<=4;i++) 
	{
	div=pri[0]/pri[i];
	exgcd(div,pri[i]); a=(a%pri[i]+pri[i])%pri[i];
//		cout<<div<<" "<<a<<" "<<a*div%pri[0]<<endl;
	ans=(ans+x[i]*div*a)%pri[0];
	}
//	cout<<ans<<" "<<d<<endl;
	return ans%pri[0];
}

int main()
{
    cin>>n>>g;
    for (int i=1;i<=4;i++)
    {	jc[0][i]=inv[1][i]=inv[0][i]=ninv[0][i]=ninv[1][i]=1; ll pp=pri[i];
        for (int j=1;j<pri[i];j++) jc[j][i]=jc[j-1][i]*j%pp;
        for (int j=2;j<pri[i];j++) inv[j][i]=((-pp/j*inv[pp%j][i])%pp+pp)%pp,
        ninv[j][i]=inv[j][i]*ninv[j-1][i]%pp;
    }//O(n)预处理逆元啥的
	for (int i=1;i<=sqrt(n);i++)  
    if (n%i==0) {
//		cout<<i<<" "<<n/i<<":"<<endl;
        k=k%pri[0]+find(i)%pri[0];
        if (i*i!=n) k=k%pri[0]+find(n/i)%pri[0];

    }
//		cout<<k<<endl;
    cout<<ksm(g,k,p)<<endl;
    return 0;
}

数论还有很多要学，但蒟蒻最近不想搞数论了_(:з」∠)，如果有问题欢迎提出。