涉及质数的时间复杂度都是玄学的。
——题记
由整数唯一分解定理：\(\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\)，多剪枝就好了
——后记