首页 > 代码库 > BZOJ 3629 JLOI2014 聪明的燕姿 约数和+DFS
BZOJ 3629 JLOI2014 聪明的燕姿 约数和+DFS
根据约数和公式来拆s,最后再把答案乘出来,我们发先这样的话递归层数不会太大每层枚举次数也不会太多,然而我们再来个剪枝就好了
#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<vector> using namespace std; inline int read() { int sum=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) { sum=(sum<<1)+(sum<<3)+ch-‘0‘; ch=getchar(); } return sum; } vector<int> ans; int is[50000],Max=50000,prime[50000],sz; inline void Init() { for(int i=2;i<Max;i++) { if(!is[i]) prime[++sz]=i; for(int j=1;prime[j]*i<Max;j++) { is[prime[j]*i]=1; if(i%prime[j]==0)break; } } } inline bool jud(int x) { if(x==1)return 0; int lim=(int)sqrt(x+0.5); for(int i=1;prime[i]<=lim;i++) if(x%prime[i]==0) return 0; return 1; } void dfs(int x,int s,int Ans) { if(s==1) { ans.push_back(Ans); return; } int lim=(int)sqrt(s+0.5); if(prime[x]>lim) { if(jud(s-1)&&s-1>=prime[x]) { Ans*=s-1; ans.push_back(Ans); } return; } long long sum=0,get=1; for(int i=0;sum<=s;i++) { sum+=get; if(s%sum==0) dfs(x+1,s/sum,Ans*get); get*=prime[x]; } } int main() { //freopen("swallow.in","r",stdin); //freopen("swallow.out","w",stdout); int s; Init(); while(scanf("%d",&s)==1) { ans.clear(); dfs(1,s,1); printf("%d\n",ans.size()); if(ans.size()==0)continue; sort(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) printf("%d ",ans[i]); printf("\n"); } return 0; }
BZOJ 3629 JLOI2014 聪明的燕姿 约数和+DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。