P4397聪明的燕姿 题解 & Miller~Rabin 质数判定

涉及质数的时间复杂度都是玄学的。

——题记

传送门

由整数唯一分解定理：\(\coprod\limits_{i=1}^{k}p_i^{c_i}\)

有该正整数的正约数为：\(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^j)\)

即我们要求有多少个数满足 \(\coprod\limits_{i=1}^k(\sum\limits_{j=0}^{c_i}p_i^j)=S\)

然后就搜索 \(+\) 剪枝：

枚举第 \(i\) 个质数是否出现，出现多少次，显然是对的。

优化 \(1\) ：当我们枚举到的质数大于 \(\sqrt S\) 时，我们直接判断 \(S-1\) 是不是质数即可，因为此时任意 \(p^2>S\)

优化 \(2\) ：当要判断大于 \(1e6\) 的数是否为质数时，使用 \(Miller~Rabin\) 质数判定

扩：\(Miller~Rabin\) 质数判定：

首先：该算法本质上是一种随机化算法，能在\(O(k log^3 n)\)的时间复杂度下快速判断出一个数是否是素数，但具有一定的错误概率。不过在一定数据范围内，通过一些技巧可以使其不出错。

由费马小定理可知：对任意素数 \(p\) 和与其互质的整数 \(a\)，有 \(a^{p-1}\equiv 1~(\bmod p)\)

考虑将其逆过来，对一个数 \(p\)，随机选取一个小于它的 \(a\)，若 \(a^{p-1}\equiv 1~(\bmod p)\)，是否可以证明它是质数

很明显是不可以的，一个反例就是 \(561\)（当然这种数有无限个，可以去搜卡迈克尔数）

引入二次探测定理：对于质数 \(p\) 若 \(x^2\equiv 1~(\bmod p)\)，则小于 \(p\) 的解只有两个： \(x=1\) 或 \(x=p-1\)

证明：

原式可以转换为 \(x^2-1\equiv 0~(\bmod p)=>(x+1)(x-1)\equiv 0~(\bmod p)\)，因为 \(p\) 的因数只有 \(1\) 和 \(p\)，所以小于 \(p\) 的解只有 \(x=1\) 或 \(x=p-1\)，

证毕

然后考虑结合两个定理，进行素数判断。

对于 \(p-1\)，若它为奇数，直接特判

否则将它分为 \(2^k\times t\)(\(t\) 为奇数)，随机选取一个 \(a\)，先计算 \(a^t\)，然后让其自乘，判断其解是否全为 \(1\) ，或者在非最后一个数的情况下出现 \(p-1\)

如果都满足，则我们认为这个数是质数

因为错误率是 \(\frac{1}{4}\)

所以我们可以选 \(2,3,5,7,11,13,17,19\) 多个数进行判断，降低错误率

当然，也可以选择背诵

\(int\) 范围内选 \(\{2,7,61\}\)

\(long~long\) 范围内选 \(\{2,325,9375,28178,450775,9780504,1795265022\}\)

可以保证 \(100\%\) 不会错

因为数已经定下来，所以可能会导致选的数是 \(p\) 的倍数，这是要特判，然后 \(continue\)

最后，分析一下该算法时间复杂度：一次找到答案的时间不会超过 \(\sqrt S\)，所以时间复杂度是 \(O(Ans\sqrt S)\)，玄学至极

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int T,S;
int ans[N],tot;
bool prime[N];
int zs[N],idx;
int ksm(int ds,int zs,int mod)
{
	int re=1;
	while(zs)
	{
		if(zs&1) re=1ll*ds*re%mod;
		ds=1ll*ds*ds%mod;
		zs=zs/2;
	}
	return re;
}
bool MRtest(int x)
{
	if(x%2==0||x<3) return x==2;
	int zs=x-1,sl=0;
	while(zs%2==0) zs=zs/2,sl++;
	int ud[3]={2,7,61};
	for(int i=0;i<3;i++)
	{
		int v=ksm(ud[i],zs,x);
		if(v==1||v==x-1||v==0) continue;
		for(int j=1;j<=sl;j++)
		{
			v=1ll*v*v%x;
			if(v==x-1&&j!=sl){v=1;break;}
			if(v==1) return false;
		}
		if(v!=1) return false;
	}
	return true;
}
void dfs(int wz,int sum,int now)
{
	if(sum==1)
	{
		ans[++tot]=now;
		return ;
	}
	if(sum<zs[wz]+1) return ;
	if(MRtest(sum-1)) ans[++tot]=(sum-1)*now;
	for(int i=wz;zs[i]*zs[i]<=sum;i++)
	{
		int zh=zs[i]+1,t=zs[i];
		for(;zh<=sum;t*=zs[i],zh+=t)
			if(sum%zh==0)
				dfs(i+1,sum/zh,now*t);
	}
}
signed main()
{
	prime[1]=true;
	for(int i=2;i<=100000;i++)
	{
		if(!prime[i]) zs[++idx]=i;
		for(int j=1;j<=idx&&zs[j]*i<=100000;j++)
		{
			prime[zs[j]*i]=true;
			if(i%zs[j]==0) break;
		}
	}
	while(scanf("%lld",&S)!=EOF)
	{
		tot=0;
		dfs(1,S,1);
		sort(ans+1,ans+tot+1);
		printf("%lld\n",tot);
		for(int i=1;i<=tot;i++)
		printf("%lld ",ans[i]);
		if(tot!=0) puts("");
	}
	return 0;
}

遇到质数的题，大胆\(DFS\)，多剪枝就好了

——后记