反素数

反素数资料

http://codeforces.com/problemset/problem/27/E

E. Number With The Given Amount Of Divisors time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Given the number n, find the smallest positive integer which has exactly n divisors. It is guaranteed that for the given n the answer will not exceed 1018.

Input

The first line of the input contains integer n (1 ≤ n ≤ 1000).

Output

Output the smallest positive integer with exactly n divisors.

Examples input 4 output 6 input 6 output 12

#include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 1e5+10; const int mod = N; typedef unsigned long long LL; int vis[N], prime[N]; int k, n; const LL inf = ~0LL; LL ans; void dfs(int pos,LL tmp,int num) { if(num>n) return ; if(num==n) { if(tmp<ans) ans=tmp; return ; } for(int i=1;i<=63;i++) { if(tmp*prime[pos]>ans) break; dfs(pos+1,tmp*=prime[pos],num*(i+1)); } return ; } int main() { memset(vis,0,sizeof(vis)); k=0; for(int i=2;i<N;i++) { if(vis[i]) continue; if(k>=20) break; prime[k++]=i; for(int j=2*i;j<N;j+=i) vis[j]=1; } scanf("%d", &n); ans=inf; dfs(0,1,1); cout<<ans<<endl; return 0; }

1060 最复杂的数 题目来源：  Ural 1748 基准时间限制：1 秒 空间限制：131072 KB 分值: 40  难度：4级算法题  收藏  关注 把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。 例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。 Input 第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 100) 第2 - T + 1行：T个数，表示需要计算的n。（1 <= n <= 10^18) Output 共T行，每行2个数用空格分开，第1个数是答案，第2个数是约数的数量。 Input示例 5 1 10 100 1000 10000 Output示例 1 1 6 4 60 12 840 32 7560 64 #include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 1e5+10; const int mod = N; typedef unsigned long long LL; int vis[N]; LL prime[N]; int k; const LL inf = ~0LL; LL ans, ansnum, n; void dfs1(int pos,int x,LL tmp,LL num) { if(pos>=16) return ; if(ansnum<num) { ans=tmp, ansnum=num; } if(ansnum==num&&tmp<ans) { ans=tmp; } for(LL i=1; i<=x; i++) { if(tmp>n/prime[pos]) break; dfs1(pos+1,i,tmp*=prime[pos],num*(i+1)); } return ; } void dfs(int dept,int x,LL tmp,int num) { //到叶子结点，返回 if(dept >= 16) return; //num记录的因子个数，如果遇到更小的，就更新 if(num > ansnum) { ansnum = num; ans = tmp; } //当因子个数相同时，取值最小的 if(num == ansnum && ans > tmp) ans = tmp; for(int i=1;i<=x;i++) { if(n / prime[dept] < tmp) break; dfs(dept+1,i,tmp *= prime[dept],num*(i+1)); } } int main() { int t; memset(vis,0,sizeof(vis)); k=0; for(LL i=2; i<N; i++) { if(vis[i]) continue; if(k>=17) break; prime[k++]=i; for(int j=2*i; j<N; j+=i) vis[j]=1; } scanf("%d", &t); while(t--) { scanf("%lld", &n); ans=inf, ansnum=0; dfs1(0,60,1,1); printf("%lld %lld\n",ans,ansnum); } return 0; }