P4397 [JLOI2014]聪明的燕姿
2024-09-04 16:01:59
P4397 [JLOI2014]聪明的燕姿
题目背景
阴天傍晚车窗外
未来有一个人在等待
向左向右向前看
爱要拐几个弯才来
我遇见谁会有怎样的对白
我等的人他在多远的未来
我听见风来自地铁和人海
我排着队拿着爱的号码牌
题目描述
城市中人们总是拿着号码牌,不停寻找,不断匹配,可是谁也不知道自己等的那个人是谁。
可是燕姿不一样,燕姿知道自己等的人是谁,因为燕姿数学学得好!燕姿发现了一个神奇的算法:假设自己的号码牌上写着数字 \(S\),那么自己等的人手上的号码牌数字的所有正约数之和必定等于 \(S\)。
所以燕姿总是拿着号码牌在地铁和人海找数字(喂!这样真的靠谱吗)可是她忙着唱《绿光》,想拜托你写一个程序能够快速地找到所有自己等的人。
输入输出格式
输入格式:
输入包含 \(k\) 组数据。 对于每组数据,输入包含一个号码牌\(S\)。
输出格式:
对于每组数据,输出有两行,第一行包含一个整数 \(m\),表示有 \(m\) 个等的人。
第二行包含相应的 \(m\) 个数,表示所有等的人的号码牌。
注意:你输出的号码牌必须按照升序排列。
说明
对于 \(100\%\) 的数据,\(k \le 100\), \(S \le 2 \times 10^9\) 。
唯一分解
\(S=\prod p_i^{c^i}\)
约数和\(\sigma(S)=\prod \sum_{i=0}^{c^i} p_i^i\)
然后可以直接搜索\(c\)和\(p\)
注意一些边界情况即可
Code:
#include <cstdio>
#include <algorithm>
const int N=1e7;
int pri[N+10],ispri[N+10],cnt,k,tot,s[N];
void init()
{
for(int i=2;i<=N;i++)
{
if(!ispri[i])
pri[++cnt]=i;
for(int j=1;j<=cnt&&pri[j]*i<=N;j++)
{
ispri[pri[j]*i]=1;
if(i%pri[j]==0) break;
}
}
}
bool check(int p,int dep)
{
if(p<=N) return !ispri[p]&&p>=pri[dep];
for(int i=1;pri[i]<=46340&&pri[i]*pri[i]<=p;i++)
if(p%pri[i]==0) return false;
return true;
}
void dfs(int res,int dep,int num)
{
if(res==1) {s[++tot]=num;return;}
if(check(res-1,dep)) dfs(1,dep,(res-1)*num);
if(res<pri[dep]*pri[dep]) return;
dfs(res,dep+1,num);
int po=pri[dep]+1,hmi=pri[dep];
while(po<=res)
{
if(res%po!=0)
{
po=po*pri[dep]+1,hmi*=pri[dep];
continue;
}
dfs(res/po,dep+1,num*hmi);
if(po>46340) break;
po=po*pri[dep]+1,hmi*=pri[dep];
}
}
int main()
{
init();
while(scanf("%d",&k)!=EOF)
{
tot=0;
dfs(k,1,1);
std::sort(s+1,s+1+tot);
tot=std::unique(s+1,s+1+tot)-s-1;
printf("%d\n",tot);
for(int i=1;i<=tot;i++) printf("%d ",s[i]);
if(tot) printf("\n");
}
return 0;
}
2018.10.10
最新文章
- ftp同步代码
- c# .net获取文件夹下的所有文件(多层递归),并获取区间数据(Jsion,xml等数据)写出到处理文件,学习分享~
- dos 批处学习笔记
- react-native 好多坑,记录下。
- wget ftp
- 我给女朋友讲编程html系列(4) -- html常用简单标签
- CoreData 基本操作方法封装
- bootstrap的滚动监听
- ubuntu12.04 U盘自动挂载配置
- MAC终端显示隐藏文件,关闭显示
- .net常見面試題(一)
- Linux 关于解压
- Bad Hair Day(单调栈 )
- Android:ViewPager04
- Javascript异步数据的同步处理方法
- 静态库 .a 转成共享库 .so
- php如何上传txt文件,并且读取txt文件
- jsvascript === 和==的区别
- what&#39;s the 灰盒测试
- 忘记秘密利用python模拟登录暴力破解秘密
热门文章
- 洛谷P3611 [USACO17JAN]Cow Dance Show奶牛舞蹈
- Jenkins搭建CI/CD
- Centos7-Mysql-5.6.41一主两从的搭建
- JAVA / MySql 编程—— 第四章 高级查询(二)
- Numpy安装报错:试过N种安装方法终于
- Git ---游离状态下的commit 分支切换与找回,commit之后无法找到历史记录
- ELK之Elasticsearch
- Background Segment CNT
- CONDENSE命令により、文字列から冗長スペースが削除
- The Road to learn React书籍学习笔记(第一章)