首页 > 代码库 > ZOJ 1562 More Divisors 反素数
ZOJ 1562 More Divisors 反素数
最裸的反素数问题。求不大于N的数约数最多的数是多少，如果有多个求最小值。
设x的约数个数为g(x)，如果有某个正整数a有对于任意0<i<a有g(i)<g(a)，则称a为反素数。
g(x)的计算方法，先分解质因子x=a^b*c^d*e^f…
g(x)=(b+1)*(d+1)*(f+1)，即指数+1的乘积
反素数有性质：
一个反素数的质因子必然是从2开始的连续质数
2^t1*3^t2*5^t3*7^t4.....必然有t1>=t2>=t3>=....
有了这些性质之后，就可以用dfs搜索质因子来求值了
搜索过程如下：
在保证性质1和2的情况下构造出一定长度的指数数组，指数数组的每一个情况就相当于一个数，即1-x当中x拥有最多的约数（但不保证唯一），并且dfs的过程中也可以得到约数个数，约数个数相等的时候，得到的最小的值就是反素数，也就是本题所要求的解。
#include <cstdio>#include <sstream>#include <fstream>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <cctype>#include <ctime>#include <set>#include <climits>#include <vector>#include <queue>#include <stack>#include <cstdlib>#include <cmath>#include <string>#include <list>#define INPUT_FILE "in.txt"#define OUTPUT_FILE "out.txt"using namespace std;typedef long long LL;const int INF = INT_MAX / 2;void setfile() { freopen(INPUT_FILE,"r",stdin); freopen(OUTPUT_FILE,"w",stdout);}int prime[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};int times[20];LL ans,anscnt;void dfs(LL curval,LL curcnt,int nowt,LL lim) { if(nowt >= 20) return; if(curcnt > anscnt) { anscnt = curcnt; ans = curval; } if(curcnt == anscnt) { ans = min(curval,ans); } for(int i = 1;i < 80;i++) { if(nowt == 0 || i <= times[nowt - 1]) { curval *= prime[nowt]; curcnt = curcnt / i * (i + 1); times[nowt] = i; if(curval > lim) return; dfs(curval,curcnt,nowt + 1,lim); } else break; }}int main() { LL lim; while(cin >> lim) { memset(times,0,sizeof(times)); ans = anscnt = 0; dfs(1,1,0,lim); cout << ans << endl; } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。