这道题考试选择打表,完美爆零。。
算数基本定理:
任何一个大于1的自然数N,都可以唯一分解成有限个质数的乘积N=P₁^a₁ P₂^a₂…Pn^an,这里P₁<P₂<…<Pn均为质数,其诸指数ai是正整数。
这样的分解称为N的标准分解式。
约数和定理:
对于任意一个大于1的正整数N可以分解正整数:N=P₁^a₁ P₂^a₂…Pn^an,则由约数个数定理可知N的正约数有(a₁+1)(a₂+1)(a₃+1)…(an+1)个,那么N的(a₁+1)(a₂+1)(a₃+1)…(an+1)个正约数的和为f(N)=(P₁^0+P₁^1+P₁^2+…P₁^a₁)(P₂^0+P₂^1+P₂^2+…P₂^a₂)…(Pn^0+Pn^1+Pn^2+…Pn^an)。
至此,搜索算法很显然地露出水面——穷举Pi及其对应的ai进行搜索。
具体解释:
题目给的n可以分解为多个式子的乘积,式子中是互不相同质数的幂依次增加的和(如上图黄色部分)。每个式子最高次幂那一项的数的乘积即为所得答案之一(如上图绿色部分)。它的所有正约数之和为题目给的
n。
在深搜时要注意:有两种情况:①最后分解完,剩余得1,将所得结果记录②分解剩余的数-1是一个质数p,这样就可以看成p^0+p^1,也可以得到结果,将其记录(代码中有标注)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define pos2(i,a,b) for(int i=(a);i>=(b);i--) #define ll long long #define N 100100 using namespace std; ll prime[N],ans[N],sum,n; bool notprime[N]; int cnt; void getprime()//预处理出所有素数 { pos(i,2,N) { if(!notprime[i]) prime[++cnt]=i; for(int j=1;j<=cnt&&prime[j]*i<N;j++) { notprime[prime[j]*i]=1; if(i%prime[j]==0) break; } } } bool judge(ll x)//判断是否为素数 { if(x==1) return 0; for(ll i=1;prime[i]*prime[i]<=x;i++) if(x%prime[i]==0) return 0; return 1; } void dfs(ll now,int pos,ll left)//深搜 ,now表示目前所得的结果,pos表示搜索素数的位置,left表示目前剩余的数 { if(left==1)//①处解释 { ans[++cnt]=now; return; } if(left-1>=prime[pos]&&judge(left-1))//②处解释 ans[++cnt]=(left-1)*now; for(int i=pos;prime[i]*prime[i]<=left;i++) { for(ll tmp=prime[i]+1,tt=prime[i];tmp<=left;tt*=prime[i],tmp+=tt) if(left%tmp==0) dfs(now*tt,i+1,left/tmp); } } int main() { getprime(); while(scanf("%lld",&n)==1) { memset(ans,0,sizeof(ans)); cnt=0; dfs(1,1,n); sort(ans+1,ans+cnt+1); printf("%d\n",cnt); pos(i,1,cnt-1) printf("%lld ",ans[i]); if(cnt) printf("%d\n",ans[cnt]); } while(1); return 0; }
[BZOJ 3629][ JLOI2014 ]聪明的燕姿的更多相关文章
-
bzoj 3629 [JLOI2014]聪明的燕姿(约数和,搜索)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=3629 [题意] 给定S,找出所有约数和为S的数. [思路] 若n=p1^a1*p2^a ...
-
bzoj 3629 [JLOI2014]聪明的燕姿——约数和定理+dfs
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3629 如果要搜索,肯定得质因数分解吧:就应该朝这个方向想. **约数和定理: 对于任意一个大 ...
-
BZOJ 3629 JLOI2014 聪明的燕姿 约数和+DFS
根据约数和公式来拆s,最后再把答案乘出来,我们发先这样的话递归层数不会太大每层枚举次数也不会太多,然而我们再来个剪枝就好了 #include<cstdio> #include<ios ...
-
bzoj 3629: [JLOI2014]聪明的燕姿【线性筛+dfs】
数论+爆搜 详见这位大佬https://blog.csdn.net/eolv99/article/details/39644419 #include<iostream> #include& ...
-
BZOJ_3629_[JLOI2014]聪明的燕姿_dfs
BZOJ_3629_[JLOI2014]聪明的燕姿_dfs Description 阴天傍晚车窗外 未来有一个人在等待 向左向右向前看 爱要拐几个弯才来 我遇见谁会有怎样的对白 我等的人他在多远的未来 ...
-
bzoj3629 / P4397 [JLOI2014]聪明的燕姿
P4397 [JLOI2014]聪明的燕姿 根据唯一分解定理 $n=q_{1}^{p_{1}}*q_{2}^{p_{2}}*q_{3}^{p_{3}}*......*q_{m}^{p_{m}}$ 而$ ...
-
P4397 [JLOI2014]聪明的燕姿
P4397 [JLOI2014]聪明的燕姿 题目背景 阴天傍晚车窗外 未来有一个人在等待 向左向右向前看 爱要拐几个弯才来 我遇见谁会有怎样的对白 我等的人他在多远的未来 我听见风来自地铁和人海 我排 ...
-
【LG4397】[JLOI2014]聪明的燕姿
[LG4397][JLOI2014]聪明的燕姿 题面 洛谷 题解 考虑到约数和函数\(\sigma = \prod (1+p_i+...+p_i^{r_i})\),直接爆搜把所有数搜出来即可. 爆搜过 ...
-
[JLOI2014]聪明的燕姿(搜索)
城市中人们总是拿着号码牌,不停寻找,不断匹配,可是谁也不知道自己等的那个人是谁. 可是燕姿不一样,燕姿知道自己等的人是谁,因为燕姿数学学得好!燕姿发现了一个神奇的算法:假设自己的号码牌上写着数字 S, ...
随机推荐
-
windows下搭建nginx+php+mysql环境
一.下载需要的东西 1.nginx:http://nginx.org/en/download.html 2.php:http://php.net/downloads.php 3.mysql:(暂时先不 ...
-
Android分包方案multidex
对于功能越来越复杂的app的两大问题 问题一:当项目越来越大,方法数超过65536,编译时会出错(为什么是65536,参考下面关于dexopt对方法id检索存储介绍),这个所说的方法数包含用到的框架, ...
-
android setLayoutParams 问题,出错
LinearLayout layt = (LinearLayout) rootView.findViewById(R.id.llt_2); FrameLayout.LayoutParams layou ...
-
JDBC进行批处理
转自 http://mousepc.iteye.com/blog/1131462 业务场景:当需要向数据库发送一批SQL语句执行时,应避免向数据库一条条的发送执行,而应采用JDBC的批处理机制,以提升 ...
-
Dapper.ColumnMapper 的使用
using System; using System.Collections.Generic; using System.Data; using System.Data.SqlClient; usin ...
-
使用 testng.xml 参数化
1. 创建 Java 测试类 2. 添加测试方法 TestngParameterTest(String name, String age) 3. 为测试方法添加注释 @Parameters({&quo ...
-
oracle 日志学习(转载)
一,重做日志概念 重做日志文件(redo log file)对于Oracle数据库至关重要.它们是数据库的事务日志.通常只用于恢复,不过也可以用于以下工作: q 系统崩溃后的实例恢复 q 通过备份恢复 ...
-
mysql 在启动时配置文件的查找方式
知识储备: 1.mysql在启动时会去多个地方找它的配置文件,当然啦这些也都是可以从帮助中找到的,问题在于我们要知道怎么找到对应的帮助才行啊 实战: [root@workstudio data]# m ...
-
View的工作原理(一)——Measure
一.认识ViewRoot和DecorView 当Activity对象被创建的时候,会将DecorView添加到Window中,同时创建ViewRootImpl对象(ViewRoot对应于ViewRoo ...
-
201521123107 《Java程序设计》第8周学习总结
第7周作业-集合 1.本周学习总结 2.书面作业 1.List中指定元素的删除 题集jmu-Java-05-集合之4-1 1.1 实验总结 这次的函数题是编写convertStringToList和r ...