HDU4392 Maximum Number Of Divisors
2012 Multi-University Training Contest 10
1003题
给出P,找出小于等于P的一个数K,使得K的因子数最多,且K尽可能小。
广搜,每个节点包含如下记录:
K: 当前的数字
F: 因子的数量
N: 质数的数量
A[]: 每个质数的数量
易知(注:真实含义为不知道怎么证明),最终的结果一定使用的是最小的那几个质数。
所以,假设质数为prime[],坐标从0开始
添加已有质数第p个操作:
{K, F, N, A[]} → {K * prime[p], F / (A[p] + 1) * (A[p] + 2), N, A[p] + 1}
添加新的质数操作:
{K, F, N, A[]} → {K * prime[N], F * 2, N + 1, A[N] = 1}
同时根据条件,在F相同时,可以删除较大的K。
这里用map记录F到一个节点的映射,只需保留最小的K的情况。
答案随着P有单调的关系,所以可以在一开始将所有的P读入进来,一次广搜就可以得到所有答案。
[java]
import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
class Node
{
private static final int MAXP = 60;
public BigInteger K;
public long F;
public int N;
public int[] A;
public Node()
{
K = BigInteger.ZERO;
A = new int[MAXP];
}
}
public class Main
{
private static final int MAXIP = 250;
private static final int MAXP = 60;
private static BigInteger[] prime;
private static void init()
{
boolean[] isPrime = new boolean[MAXIP];
for(int i=0;i<MAXIP;++i)
{
isPrime[i] = true;
}
isPrime[0] = isPrime[1] = false;
for(int i=4;i<MAXIP;i+=2)
{
isPrime[i] = false;
}
for(int i=3;i<MAXIP;i+=2)
{
for(int j=3;i*j<MAXIP;j+=2)
{
isPrime[i*j] = false;
}
}
prime = new BigInteger[MAXP];
for(int i=0, j=0;i<MAXIP;++i)
{
if(isPrime[i])
{
prime[j++] = BigInteger.valueOf(i);
}
}
}
public static void main(String args[])
{
init();
List<BigInteger> P = new ArrayList<BigInteger>();
BigInteger MP = BigInteger.ZERO;
List<Node> ans = new ArrayList<Node>();
Scanner cin = new Scanner(new BufferedInputStream(System.in));
while(cin.hasNext())
{
BigInteger temp = new BigInteger(cin.nextLine());
P.add(temp);
if(temp.compareTo(MP) == 1)
{
MP = temp;
}
ans.add(new Node());
}
Map<Long, BigInteger> map = new HashMap<Long, BigInteger>();
Queue<Node> queue = new LinkedList<Node>();
Node origin = new Node();
origin.K = BigInteger.ONE;
origin.F = 1;
origin.N = 0;
queue.add(origin);
map.put(origin.F, origin.K);
while(!queue.isEmpty())
{
Node u = queue.peek();
queue.remove();
BigInteger compare = map.get(u.F);
if(compare != null)
{
if(compare.compareTo(u.K) == -1)
{
continue;
}
}
for(int i=0;i<P.size();++i)
{
if(u.K.compareTo(P.get(i)) <= 0)
&nb
补充:软件开发 , Java ,