[BZOJ 3629][ JLOI2014 ]聪明的燕姿

时间:2022-12-16 21:59:18

这道题考试选择打表,完美爆零。。

算数基本定理:

任何一个大于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 ]聪明的燕姿的更多相关文章

  1. bzoj 3629 &lbrack;JLOI2014&rsqb;聪明的燕姿(约数和,搜索)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=3629 [题意] 给定S,找出所有约数和为S的数. [思路] 若n=p1^a1*p2^a ...

  2. bzoj 3629 &lbrack;JLOI2014&rsqb;聪明的燕姿——约数和定理&plus;dfs

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3629 如果要搜索,肯定得质因数分解吧:就应该朝这个方向想. **约数和定理: 对于任意一个大 ...

  3. BZOJ 3629 JLOI2014 聪明的燕姿 约数和&plus;DFS

    根据约数和公式来拆s,最后再把答案乘出来,我们发先这样的话递归层数不会太大每层枚举次数也不会太多,然而我们再来个剪枝就好了 #include<cstdio> #include<ios ...

  4. bzoj 3629&colon; &lbrack;JLOI2014&rsqb;聪明的燕姿【线性筛&plus;dfs】

    数论+爆搜 详见这位大佬https://blog.csdn.net/eolv99/article/details/39644419 #include<iostream> #include& ...

  5. BZOJ&lowbar;3629&lowbar;&lbrack;JLOI2014&rsqb;聪明的燕姿&lowbar;dfs

    BZOJ_3629_[JLOI2014]聪明的燕姿_dfs Description 阴天傍晚车窗外 未来有一个人在等待 向左向右向前看 爱要拐几个弯才来 我遇见谁会有怎样的对白 我等的人他在多远的未来 ...

  6. bzoj3629 &sol; P4397 &lbrack;JLOI2014&rsqb;聪明的燕姿

    P4397 [JLOI2014]聪明的燕姿 根据唯一分解定理 $n=q_{1}^{p_{1}}*q_{2}^{p_{2}}*q_{3}^{p_{3}}*......*q_{m}^{p_{m}}$ 而$ ...

  7. P4397 &lbrack;JLOI2014&rsqb;聪明的燕姿

    P4397 [JLOI2014]聪明的燕姿 题目背景 阴天傍晚车窗外 未来有一个人在等待 向左向右向前看 爱要拐几个弯才来 我遇见谁会有怎样的对白 我等的人他在多远的未来 我听见风来自地铁和人海 我排 ...

  8. 【LG4397】&lbrack;JLOI2014&rsqb;聪明的燕姿

    [LG4397][JLOI2014]聪明的燕姿 题面 洛谷 题解 考虑到约数和函数\(\sigma = \prod (1+p_i+...+p_i^{r_i})\),直接爆搜把所有数搜出来即可. 爆搜过 ...

  9. &lbrack;JLOI2014&rsqb;聪明的燕姿(搜索)

    城市中人们总是拿着号码牌,不停寻找,不断匹配,可是谁也不知道自己等的那个人是谁. 可是燕姿不一样,燕姿知道自己等的人是谁,因为燕姿数学学得好!燕姿发现了一个神奇的算法:假设自己的号码牌上写着数字 S, ...

随机推荐

  1. windows下搭建nginx&plus;php&plus;mysql环境

    一.下载需要的东西 1.nginx:http://nginx.org/en/download.html 2.php:http://php.net/downloads.php 3.mysql:(暂时先不 ...

  2. Android分包方案multidex

    对于功能越来越复杂的app的两大问题 问题一:当项目越来越大,方法数超过65536,编译时会出错(为什么是65536,参考下面关于dexopt对方法id检索存储介绍),这个所说的方法数包含用到的框架, ...

  3. android setLayoutParams 问题,出错

    LinearLayout layt = (LinearLayout) rootView.findViewById(R.id.llt_2); FrameLayout.LayoutParams layou ...

  4. JDBC进行批处理

    转自 http://mousepc.iteye.com/blog/1131462 业务场景:当需要向数据库发送一批SQL语句执行时,应避免向数据库一条条的发送执行,而应采用JDBC的批处理机制,以提升 ...

  5. Dapper&period;ColumnMapper 的使用

    using System; using System.Collections.Generic; using System.Data; using System.Data.SqlClient; usin ...

  6. 使用 testng&period;xml 参数化

    1. 创建 Java 测试类 2. 添加测试方法 TestngParameterTest(String name, String age) 3. 为测试方法添加注释 @Parameters({&quo ...

  7. oracle 日志学习(转载)

    一,重做日志概念 重做日志文件(redo log file)对于Oracle数据库至关重要.它们是数据库的事务日志.通常只用于恢复,不过也可以用于以下工作: q 系统崩溃后的实例恢复 q 通过备份恢复 ...

  8. mysql 在启动时配置文件的查找方式

    知识储备: 1.mysql在启动时会去多个地方找它的配置文件,当然啦这些也都是可以从帮助中找到的,问题在于我们要知道怎么找到对应的帮助才行啊 实战: [root@workstudio data]# m ...

  9. View的工作原理&lpar;一&rpar;——Measure

    一.认识ViewRoot和DecorView 当Activity对象被创建的时候,会将DecorView添加到Window中,同时创建ViewRootImpl对象(ViewRoot对应于ViewRoo ...

  10. 201521123107 《Java程序设计》第8周学习总结

    第7周作业-集合 1.本周学习总结 2.书面作业 1.List中指定元素的删除 题集jmu-Java-05-集合之4-1 1.1 实验总结 这次的函数题是编写convertStringToList和r ...