【acwing1296】聪明的燕姿（搜索，因数分解）-阿南达文事网

【acwing1296】聪明的燕姿（搜索，因数分解）

题目链接：/

题意：
我们称形如 1 + p 1 + p 2 + . . . + p k 1 + p^1 + p^2 + ... + p^k 1+p1+p2+...+pk是一个关于素数 p p p的“素数链”。题目即要求：对于一个数 S ( < = 2 e 9 ) S ( <= 2e9) S(<=2e9)，能够由多少“素数链”相乘得到。
例如题目的样例： S = 42 S = 42 S=42它可以由 ( 1 + 2 + 2 2 ) ( 1 + 5 ) (1+2+2^2)(1+5) (1+2+22)(1+5)这两个素数链相乘得到。值得注意的是，不同的素数链的素数一定是不同的，如 21 21 21 不能分解为 ( 1 + 2 + 2 2 ) ( 1 + 2 ) (1+2+2^2)(1+2) (1+2+22)(1+2)。原因在于两条“素数链”对应的素数相同。

个人思路：
暴搜。每层探讨素数选几个（至少为0个），不同层考虑不同的素数。即每一层考虑一个素数链的长度，而不同层考虑不同的素数。
然而代码是超时的……

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;
const int N = 1e5+5; 
vector<int> pm;
vector<int> pw[N],presum[N];
bool np[N];
int pos[N];
void Init(){np[0] = np[1] = 1;for(int i = 2;i < N;i++){if(!np[i]){pos[i] = pm.size();pm.push_back(i);}int sz = pm.size();for(int j = 0;j < sz && (ll)pm[j]*i < N;j++){np[pm[j]*i] = true;if(i%pm[j] == 0){break;}}}int sz = pm.size();for(int i = 0;i < sz;i++){pw[i].push_back(1);while(1){ll t = (ll)pw[i].back()*pm[i];if(t > 2e9)break;pw[i].push_back((int)t);}}for(int i = 0;i < sz;i++){presum[i].push_back(1);int tsz = pw[i].size();for(int j = 0;j < tsz;j++){ll t = presum[i].back() + (ll)pw[i][j]*pm[i];if(t > 2e9)break;presum[i].push_back((int)t);}}return ;
}ll S;
set<int> ans;
int use[N];
int maxl;int process(int up){int ans = 1;for(int i = 0;i < up;i++)	{ans *= pw[i][use[i]];}return ans;
}bool is_prime(ll x){if(x == 1)	return false;for(int i = 0;(ll)pm[i]*pm[i] <= x;i++)	{if(x%pm[i] == 0)return false;}return true;
}void dfs(int dp,ll x){if(x == 1){ans.insert(process(dp));return ;}if(dp == maxl){		if(is_prime(x - 1) && ((x-1) >= pm[maxl] || ((x-1) < pm[maxl] && !use[pos[x-1]]))){ans.insert(process(dp)*(x-1));}return ;}//dp means the levelint sz = presum[dp].size();for(int i = 0;i < sz && presum[dp][i] <= x;i++){if(x % presum[dp][i] == 0){use[dp] = i;dfs(dp + 1,x / presum[dp][i]);}}return ;
}int main(){Init(); while(scanf("%lld",&S) != EOF){ans.clear();for(maxl = 0;maxl < pm.size() && (ll)pm[maxl]*pm[maxl] <= S;maxl++); dfs(0,S);printf("%d\n",ans.size());for(auto u:ans)printf("%d ",u);if(ans.size())printf("\n");}return 0;
}

对于本代码超时的原因，应该是在每层对于 p 0 p^0 p0都进行了考虑，这样会导致递归层数很多，但许多递归都是无效的。正确的搜索思路是，在每一层枚举每个素数以及素数的数量。例如当枚举到素数 2 2 2时，我们应当尝试从 ( 1 + 2 1 ) (1 + 2^1) (1+21), ( 1 + 2 1 + 2 2 ) (1 + 2^1 + 2^2) (1+21+22)…枚举，看是否能够整除 S S S.
注意，我们在每一层的S的试除中，都仅需要枚举到 S \sqrt{S} S 的素数，这样大大降低了时间复杂度。

AC代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N = 5e4+5;
bool np[N];
int pos[N];
vector<int> vc;
typedef long long ll;
void Init(){np[0] = np[1] = 1;for(int i = 2;i < N;i++){if(!np[i]){pos[i] = vc.size();vc.push_back(i);}int sz = vc.size();for(int j = 0;j < sz && (ll)vc[j]*i < N;j++){np[vc[j]*i] = true;if(i%vc[j] == 0)break;}}
}bool isprime(ll x){for(int i = 0;(ll)vc[i]*vc[i] <= x;i++){if(x%vc[i] == 0){return false;}} return true;
}set<int> s;
void dfs(int last,int prod,ll S){if(S == 1){s.insert(prod);return ;}if((S - 1>(last == -1?0:vc[last])) && isprime(S-1)){s.insert(prod*(S-1));}for(int i = last + 1;(ll)vc[i]*vc[i] <= S;i++){for(ll j = 1 + (ll)vc[i],tmp = (ll)vc[i]*vc[i];j <= S;j += tmp,tmp*=(ll)vc[i]){if(S % j == 0){//cout << S << " " << j << " " << tmp << endl; dfs(i,tmp/vc[i]*prod,S / j);}}}
}int main(){Init();ll S;while(scanf("%lld",&S) != EOF){s.clear();dfs(-1,1,S);printf("%d\n",s.size());for(auto u:s){printf("%d ",u);}if(s.size())printf("\n");}return 0;
}