题目大意:
给定数列 a1 , a2 , ... , an
希望找到一个 N = sigma(ai^ki) , (0<=ki<10) ,ki可随自己定为什么
只要保证N的因子和可以表示为 2^t的形式 , 输出t , 找不到就输出 NO
关于梅森素数,有一个重要的定理:“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次”,但是不能重复,比如说3是梅森素数,9就不满足约数和为2的幂。
还有一个重要内容就是,N的约数和幂次是可以直接由构成它的梅森素数的来源幂次相加而得的。
“一个数能够写成几个不重复的梅森素数的乘积” 等价于 “这个数的约数和是2的幂次” 因为这两个概念是充分必要的
那么就说明在这里要找到一个N表示为几个梅森素数的乘积,那么很明显,这里的ki只能是 0或者1 , 因为只要乘方了,那么必然那个数要么无法用梅森素数的乘积表示
要么乘积中存在重复的梅森素数
这里数字小于 2^31 , 在这个范围内只有 8个梅森素数
一个个枚举跑一遍就行了,最后结合得到答案,可以利用简单的dp背包的思想
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
using namespace std;
#define pii pair<int,int>
const int p[] = {,,,,,,,}; //mason数的p的位置,表示为2^p-1
int mason[] , len[(<<)] , rec[(<<)] , tot;
bool vis[(<<)];
set<int> st; int Mason(int b){return (<<b)-;} void get_mason(){for(int i= ; i< ; i++)mason[i] = Mason(p[i]);} void init()
{
int all = (<<);
for(int i= ; i<all ; i++){
int t = ;
for(int j= ; j< ; j++)
if(i&(<<j)) t+=p[j];
len[i] = t;
}
} int ok(int x)
{
int cur = ;
for(int i= ; i< ; i++){
if(x%mason[i]==){
x /= mason[i];
cur|=(<<i);
}
}
if(x>) cur = ;
return cur;
} int main()
{
// freopen("a.in" , "r" , stdin);
get_mason();
init();
int n , a;
while(~scanf("%d" , &n)){
st.clear();
for(int i= ; i<n ; i++){
scanf("%d" , &a);
int state = ok(a);
if(state) st.insert(state);
} memset(vis , , sizeof(vis));
tot = ;
set<int>::iterator it=st.begin();
for( ; it!=st.end() ; it++) rec[tot++] = *it;
int all = (<<);
vis[] = true;
for(int i= ; i<tot ; i++){
for(int j=all- ; j>=rec[i] ; j--)
if((rec[i]&j) == rec[i]) vis[j] = vis[j-rec[i]] | vis[j];
}
int ret = ;
for(int j= ; j<all ; j++)
if(vis[j]) ret = max(ret , len[j]);
if(ret) printf("%d\n" , ret);
else puts("NO");
}
return ;
}
POJ 1777 mason素数的更多相关文章
-
POJ 1845 Sumdiv [素数分解 快速幂取模 二分求和等比数列]
传送门:http://poj.org/problem?id=1845 大致题意: 求A^B的所有约数(即因子)之和,并对其取模 9901再输出. 解题基础: 1) 整数的唯一分解定理: 任意正整数都有 ...
-
POJ 1811 大素数判断
数据范围很大,用米勒罗宾测试和Pollard_Rho法可以分解大数. 模板在代码中 O.O #include <iostream> #include <cstdio> #inc ...
-
poj 2262【素数表的应用---判断素数】【哈希】
Goldbach's Conjecture Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 35214 Accepted: ...
-
poj 2689 巧妙地运用素数筛选
称号: 给出一个区间[L,R]求在该区间内的素数最短,最长距离. (R < 2 * 10^9 , R - L <= 10 ^ 6) 由数论知识可得一个数的因子可在开根号内得到. 所以,我们 ...
-
POJ - 3126 bfs + 素数筛法 [kuangbin带你飞]专题一
题意:给定两个四位素数作为终点和起点,每次可以改变起点数的某一位,且改变后的数仍然是素数,问是否可能变换成终点数字? 思路:bfs搜索,每次改变四位数中的某一位.素数打表方便判断新生成的数是否是素数. ...
-
poj 1811 随机素数和大数分解(模板)
Sample Input 2 5 10 Sample Output Prime 2 模板学习: 判断是否是素数,数据很大,所以用miller,不是的话再用pollard rho分解 miller : ...
-
poj 2689 (素数二次筛选)
Sample Input 2 17 14 17 Sample Output 2,3 are closest, 7,11 are most distant. There are no adjacent ...
-
poj 2992 Divisors (素数打表+阶乘因子求解)
Divisors Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9617 Accepted: 2821 Descript ...
-
POJ 1777
一道好题. 由算术基本定理,知: 那么,对于上式的每个因子值只能是2^M的形式.取第一个式子为例,通过分解因式出(1+p^2)=2^k知,a只能为1. 于是对于p只能是梅森素数.而且每个梅森素数只能出 ...
随机推荐
-
for语句嵌套循坏性能的剖析
日常工作中,处理数据难免会遇到遍历,for循环可能是我们用的比较多的了.本节就来探讨下for语句嵌套循环的性能,猜想下面两个语句的性能. 语句1 ; i < ; i++){ ; j < ; ...
-
CSS控制样式的三种方式优先级对比验证
入职已经一个月了,自此后,就好久没有写过博客了,在此先跟关注我的博友们说声抱歉.今天,在公司的一个培训作业的驱动以及伟哥那句“再不写博客就开除你”的监督下,我终于重拾旧爱,再次登录博客园,继续与大家分 ...
-
elasticsearch插件之一:bigdesk
bigdesk是elasticsearch的一个集群监控工具,可以通过它来查看es集群的各种状态,如:cpu.内存使用情况,索引数据.搜索情况,http连接数等. 可用项目git地址:https:// ...
-
leetcode || 53、Maximum Subarray
problem: Find the contiguous subarray within an array (containing at least one number) which has the ...
-
python 字符转换
我们所看到的“明文字符串”,都是经过编码(比如ASCII.Uncoded.UTF-8.GB-2312等)后呈现在我们面前的. 文本中“3082”想要“所见到所得”到内存中处理,必须decode('he ...
-
mysql主从同步+mycat读写分离+.NET程序连接mycat代理
背景 最近新项目需要用到mysql数据库,并且由于数据量大的原因,故打算采用1主1从(主数据库负责增.删.改操作:从数据库负责查操作)的数据库架构,在实现主从之后还要实现读写分离的代理,在网上搜寻了很 ...
-
LXC学习实践(3)快速体验第一个容器
1.搭建第一个 LXC 虚拟计算机 #yum install lxc* 2.安装软件包后要检查 Linux 发行版的内核对 LXC 的支持情况,可以使用下面命令 #lxc-checkconfig #l ...
-
【DFS】困难的串
题目: 问题描述:如果一个字符串包含两个相邻的重复子串,则称它为容易的串,其他串称为困难的串.如:BB,ABCDACABCAB,ABCDABCD都是容易的,A,AB,ABA,D,DC,ABDAB,CB ...
-
POJ 2987 Firing (最大权闭合图)
Firing Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 12108 Accepted: 3666 Descript ...
-
ASCS HA
Please let us know what do you mean by "the PAS can not be accessed", what error did you f ...