数学------------数论（18）
数学--杂（14）
反素数的定义：对于任何正整数，其约数个数记为，例如，如果某个正整数满足：对任意的正整
&&&&&&&&&&& 数，都有，那么称为反素数。
从反素数的定义中可以看出两个性质：
（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小
（2）同样的道理，如果，那么必有
个人理解性证明：
对（1）假设不是从2开始，那么假设n的最小素因素是k，把k换成2，2的次数仍等于k的次数，得到N，可知,N&n，并且f(n)==f(N)，与n是反素数矛盾
对(2)假设ti&tj & ti,tj分别是是质因数i,j的次数，i&j，那么将i的次数换成tj,j的次数换成ti 可以得到N ，满足N&n且f(n)==f(N)，与n是反素数矛盾
综上，两条性质得证
可能会疑惑，反素数的性质有个毛用！？
答案是：剪枝
先来一份TLE代码(2000ms+)
const int SIZE = 16;
const int MAXN = 65;
int p[SIZE] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
void dfs(int dep, ll tmp , ll mx)
if(tmp&=n)
if(mx&ansnum)
if(mx==ansnum)ans=min(tmp,ans);///
if(tmp&=n || dep&SIZE-1)
for(int i=0;i&SIZE;i++)
if(n/tt&tmp)
dfs(dep+1,tmp*tt,mx*(i+1));
tt*=p[dep];
int main()
//IN(&zoj1562.txt&);
while(~scanf(&%lld&,&n))
ans=ansnum=0;
dfs(0,1,1);
printf(&%lld\n&,ans);
TLE的原因是dfs太多，剪枝方法很简单，
1、DFS的时候，是从小的素数开始，由性质1，必须是次数从1开始而不是0开始，这样就剪下了一块
2、DFS的时候，深度为dep的那一层，循环处理的是prm[dep]的i次方，那么由性质2，其上限不能超过上一层的次数，又零零碎碎剪下了不少
另外注意两点：
1、因为害怕超过long long 所以用除法
if(n/tt&tmp)
2、注意求反素数这行代码：（是为了满足定义）
&pre code_snippet_id=&457113& snippet_file_name=&blog__8087056& name=&code& class=&cpp&&if(mx==ansnum)ans=min(tmp,ans);
#include &cstdio&
#include &cstring&
#include &algorithm&
#include &string&
#include &iostream&
#include &iomanip&
#include &cmath&
#include &map&
#include &set&
#include &queue&
#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i&e;i++)
#define repe(i,s,e) for(int i=s;i&=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,&r&,stdin)
#define OUT(s) freopen(s,&w&,stdout)
const ll ll_INF = ((ull)(-1))&&1;
const double EPS = 1e-8;
const int INF = ;
const int SIZE = 16;
const int MAXN = 65;
int p[SIZE] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
void dfs(int dep, ll tmp , ll mx,int num)
if(tmp&=n)
if(mx&ansnum)
if(mx==ansnum)ans=min(tmp,ans);///
if(tmp&=n || dep&SIZE-1)
for(int i=1;i&i++)
tt*=p[dep];
if(n/tt&tmp)
dfs(dep+1,tmp*tt,mx*(i+1),i+1);
int main()
//IN(&zoj1562.txt&);
while(~scanf(&%lld&,&n))
ans=ansnum=0;
dfs(0,1,1,MAXN);
printf(&%lld\n&,ans);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：259806次
积分：6416
积分：6416
排名：第2809名
原创：345篇
转载：57篇
评论：47条
(2)(1)(1)(4)(8)(11)(29)(14)(4)(4)(14)(11)(4)(11)(8)(5)(2)(3)(43)(28)(67)(46)(8)(21)(10)(10)(5)(1)(1)(14)(10)好题（115）
素数（16）
调用函数（6）
杭电（195）
Problem Description
Sample Input
Sample Output
#include&stdio.h&
int s[5010]={0,1,2,2};
for(i=4;i&5010;i++)
for(j=2;j&=i/2;j++)//i/2表示最大公约数
//for(j=2;j*j&=i;j++)
if(i%j==0)
int main()
int n,a,b,i,max,t;
scanf(&%d&,&n);
while(n--)
scanf(&%d %d&,&a,&b);
for(i=a;i&=b;i++)
if(s[i]&max)
printf(&%d\n&,t);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：98969次
积分：4113
积分：4113
排名：第5751名
原创：321篇
转载：10篇
(8)(13)(17)(7)(23)(19)(20)(9)(93)(102)(20)6477人阅读
数论（68）
今天要我要讲的是反素数，在ACM中也算是常见的考点，那么对于搞ACM的同学来说，很有必要搞清楚它，所以接下
来我会很详细地讲解。
在讲解反素数之前，我们先来看反素数的概念。
反素数的定义：对于任何正整数，其约数个数记为，例如，如果某个正整数满足：对任意的正整
&&&&&&&&&&& 数，都有，那么称为反素数。
从反素数的定义中可以看出两个性质：
（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小
（2）同样的道理，如果，那么必有
在ACM竞赛中，最常见的问题如下：
（1）给定一个数，求一个最小的正整数，使得的约数个数为
（2）求出中约数个数最多的这个数
从上面的性质中可以看出，我们要求最小的，它的约数个数为，那么可以利用搜索来解。
以前我们求一个数的所有因子也是用搜索，比如，以每一个为树的一层建立搜索树，深度为
以为例进行说明，建树如下：
可以看出从根节点到每一个叶子结点这条路径上的所有数字乘起来都是12的约数，所以12有6个约数。
搜索的思路就明显了，从根节点开始进行深搜，到叶子结点，代码如下：
void dfs(int dept,LL ans = 1)
if(dept == cnt)
fac[ct++] =
for(int i=0;i&=num[dept];i++)
dfs(dept+1,ans);
ans *= pri[dept];
回到我们的问题，同样用搜索来求最小的。
题意：给一个数，求一个最小的正整数，使得它的因子个数为。
分析：与求因子的方法类似，先建立搜索树，以每一个为一层建立树型结构，进行搜索，取最小的。
#include &iostream&
#include &string.h&
#include &stdio.h&
typedef unsigned long long ULL;
const ULL INF = ~0ULL;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
void dfs(int dept,ULL tmp,int num)
if(num & n)
if(num == n && ans & tmp) ans =
for(int i=1;i&=63;i++)
if(ans / p[dept] & tmp)
dfs(dept+1,tmp *= p[dept],num*(i+1));
int main()
while(cin&&n)
ans = INF;
dfs(0,1,1);
cout&&ans&&
题意：求以内的因子最多的那个数。
分析：基本上跟上题差不多。
#include &iostream&
#include &string.h&
#include &stdio.h&
typedef unsigned long long ULL;
const ULL INF = ~0ULL;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ULL ans,n;
void dfs(int dept,ULL tmp,int num)
//到叶子结点，返回
if(dept &= 16)
//num记录的因子个数，如果遇到更小的，就更新
if(num & best)
//当因子个数相同时，取值最小的
if(num == best && ans & tmp) ans =
for(int i=1;i&=63;i++)
if(n / p[dept] & tmp)
dfs(dept+1,tmp *= p[dept],num*(i+1));
int main()
while(cin&&n)
ans = INF;
dfs(0,1,1);
cout&&ans&&
分析：这道题主要注意数据处理。对于上面的两题，数据范围小，所以可以不用剪枝，本题就需要了。
#include &iostream&
#include &string.h&
#include &stdio.h&
typedef unsigned long long ULL;
const ULL INF = ~0ULL;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ULL ans,n;
void dfs(int dept,int limit,ULL tmp,int num)
if(tmp & n)
if(num & best)
if(num == best && ans & tmp) ans =
for(int i=1;i&=i++)
double cur = (double)
if(n & cur*p[dept])
dfs(dept+1,i,tmp *= p[dept],num*(i+1));
int main()
while(T--)
ans = INF;
dfs(0,60,1,1);
cout&&ans&&& &&&best&&
&&&给出一个数K和两个操作
&&&&如果操作是0，就求出一个最小的正整数X，满足X的约数个数为K。
&&&&如果操作是1，就求出一个最小的X，满足X的约数个数为X-K。
分析：对于操作0，就是求反素数，直接搜索搞定。对于操作1，代表1至X中不是X的约数个数为K。
#include &iostream&
#include &string.h&
#include &stdio.h&
const int N = 50005;
typedef long long LL;
const LL INF = (((LL)1)&&62)+1;
int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
void Init()
for(int i=1;i&N;i++) d[i] =
for(int i=1;i&N;i++)
for(int j=i;j&N;j+=i) d[j]--;
if(!d[d[i]]) d[d[i]] =
void dfs(int dept,int limit,LL tmp,int num)
if(num & n)
if(num == n && ans & tmp) ans =
for(int i=1;i&=i++)
if(ans / p[dept] & tmp || num*(i+1) & n)
tmp *= p[dept];
if(n % (num*(i+1)) == 0)
dfs(dept+1,i,tmp,num*(i+1));
int main()
int T,tt=1;
scanf(&%d&,&T);
while(T--)
scanf(&%d%d&,&type,&n);
if(type) ans = d[n];
ans = INF;
dfs(0,62,1,1);
printf(&Case %d: &,tt++);
if(ans == 0) puts(&Illegal&);
else if(ans &= INF) puts(&INF&);
else printf(&%I64d\n&,ans);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1442822次
积分：19035
积分：19035
排名：第324名
原创：478篇
转载：42篇
评论：356条
(1)(4)(3)(4)(38)(4)(1)(2)(5)(1)(4)(2)(1)(7)(10)(8)(8)(12)(16)(31)(20)(28)(49)(28)(17)(42)(18)(29)(26)(15)(3)(8)(9)(8)(11)(3)(46)【BZOJ1053】【HAOI2007】反素数ant 打表。/搜索
【BZOJ1053】【HAOI2007】反素数ant 打表。/搜索
[摘要：链接： #include stdio.h int main() { puts ( "转载请说明出处[vmurder]感谢" ); puts ( "网址：blog.csdn.net/vmurder/article/details/" ); } 题解： 之前玩过一件事，便是看20Y之内约数个数最多的数是哪一个]
#include &stdio.h& int main() {
puts("转载请注明出处[vmurder]谢谢");
puts("网址：blog.csdn.net/vmurder/article/details/"); }
以前玩过一件事，就是看20Y以内约数个数最多的数是哪个，约数个数是多少。
http://blog.csdn.net/vmurder/article/details/
然后记得约数个数最多1536个，那么我们对于此题就可以打表啦！
，，，上面那篇博客还是我年幼无知的产品，不能用那个来打表的。
然后有一个性质就是若x=y*k，那么x的约数个数肯定比y多对吧~
那我们就可以先打个小的质数表然后搜索找出最优点，这样或许很慢，但是有了表以后就很快啦！
#include &cstdio& using namespace std; int a[1000]={,,,,,,,,,,,,,,,,,,,,,8648640,7207200,6486480,4324320,3603600,2882880,2162160,1441440,1081080,720720,665280,554400,498960,332640,277200,221760,166320,110880,83160,55440,50400,45360,27720,25200,20160,15120,10080,7560,5040,2520,1680,1260,840,720,360,240,180,120,60,48,36,24,12,6,4,2,1,0};
int main() {
scanf("%d",&n);
for(int i=0;;i++)
if(n&=a[i])
printf("%dn",a[i]);
感谢关注 Ithao123精品文库频道，是专门为互联网人打造的学习交流平台，全面满足互联网人工作与学习需求，更多互联网资讯尽在 IThao123!
Hadoop是一个由Apache基金会所开发的分布式系统基础架构。
用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力进行高速运算和存储。
Hadoop实现了一个分布式文件系统（Hadoop Distributed File System），简称HDFS。HDFS有高容错性的特点，并且设计用来部署在低廉的（low-cost）硬件上；而且它提供高吞吐量（high throughput）来访问应用程序的数据，适合那些有着超大数据集（large data set）的应用程序。HDFS放宽了（relax）POSIX的要求，可以以流的形式访问（streaming access）文件系统中的数据。
Hadoop的框架最核心的设计就是：HDFS和MapReduce。HDFS为海量的数据提供了存储，则MapReduce为海量的数据提供了计算。
产品设计是互联网产品经理的核心能力，一个好的产品经理一定在产品设计方面有扎实的功底，本专题将从互联网产品设计的几个方面谈谈产品设计
Swift是Apple在WWDC2014所发布的一门编程语言，用来撰写OS X和iOS应用程序[1]。在设计Swift时．就有意和Objective-C共存，Objective-C是Apple操作系统在导入Swift前使用的编程语言
Swift是供iOS和OS X应用编程的新编程语言，基于C和Objective-C，而却没有C的一些兼容约束。Swift采用了安全的编程模式和添加现代的功能来使得编程更加简单、灵活和有趣。界面则基于广受人民群众爱戴的Cocoa和Cocoa Touch框架，展示了软件开发的新方向。
PHP（外文名:PHP: Hypertext Preprocessor，中文名：“超文本预处理器”）是一种通用开源脚本语言。语法吸收了C语言、Java和Perl的特点，利于学习，使用广泛，主要适用于Web开发领域。PHP 独特的语法混合了C、Java、Perl以及PHP自创的语法。它可以比CGI或者Perl更快速地执行动态网页。用PHP做出的动态页面与其他的编程语言相比，PHP是将程序嵌入到HTML（标准通用标记语言下的一个应用）文档中去执行，执行效率比完全生成HTML标记的CGI要高许多；PHP还可以执行编译后代码，编译可以达到加密和优化代码运行，使代码运行更快。
IThao123周刊(Creative Ones)
第三方登录：