首页 > 专题系列 > Java解POJ > POJ 1091 跳蚤 [解题报告] Java
2013
11-09

POJ 1091 跳蚤 [解题报告] Java

跳蚤

问题描述 :

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长,可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M,而前N个数都不超过M,卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S,然后向左,或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方,并捡起位于那里的礼物。

比如当N=2,M=18时,持有卡片(10, 15, 18)的跳蚤,就可以完成任务:他可以先向左跳10个单位长度,然后再连向左跳3次,每次15个单位长度,最后再向右连跳3次,每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤,则怎么也不可能跳到距他左边一个单位长度的地方。

当确定N和M后,显然一共有M^N张不同的卡片。现在的问题是,在这所有的卡片中,有多少张可以完成任务。

输入:

两个整数N和M(N <= 15 , M <= 100000000)。

输出:

可以完成任务的卡片数。

样例输入:

2 4

样例输出:

12

温馨提示:

这12张卡片分别是:

(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4),

(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4)

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.math.*;

public class Main{
	public static void main(String[] args){
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int m=scanner.nextInt();
		int[] yue=getYue(m);
		for (int i=0;i< yue.length ;i++ ){
			if (yue[i]==0){
				break;
			}
			m=m/yue[i];
		}
		BigInteger ok=(new BigInteger(""+m)).pow(n);
		BigInteger tmp=BigInteger.ONE;
		for (int i=0;i< yue.length ;i++ ){
			if (yue[i]==0){
				break;
			}
	         tmp=tmp.multiply(((new BigInteger(""+yue[i])).pow(n)).subtract(BigInteger.ONE));
		}
		ok=ok.multiply(tmp);
		System.out.println(ok.toString());
	}

	public static int[] getYue(int n){
		int l=0;
		int[] yue=new int[16];
		if (n%2==0){
			yue[l]=2;
			l++;
		}
		for (int i=3;i<=n/2 ;i=i+2 ){
			if (n%i==0&&isZh(i)){
				yue[l]=i;
				l++;
			}
		}
		if (isZh(n)){
			yue[l]=n;
		}
		return yue;
	}

	public static boolean isZh(int n){
		for (int i=2;i<=(int)Math.pow(n,0.5) ;i++ ){
			if (n%i==0){
				return false;
			}
		}
		return true;
	}
}

  1. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3