2013
11-10

# Jackpot

The Great Dodgers company has recently developed a brand-new playing machine.

You put a coin into the machine and pull the handle. After that it chooses some integer number. If the chosen number is zero you win a jackpot. In the other case the machine tries to divide the chosen number by the lucky numbers p1 , p2 , . . . , pn . If at least one of the remainders is zero — you win.

Great Dodgers want to calculate the probability of winning on their machine. They tried to do it, but failed. So Great Dodgers hired you to write a program that calculates the corresponding probability.

Unfortunately, probability theory does not allow you to assume that all integer numbers have equal probability. But one mathematician hinted you that the required probability can be approximated as the following limit:

limk→∞(Sk/2k+1).

Here Sk is the number of integers between -k and k that are divisible by at least one of the lucky numbers.

Input file contains n — the number of lucky numbers (1 <= n <= 16), followed by n lucky numbers (1 <= pi <= 109 ).

It is clear that the requested probability is rational. Output it as an irreducible fraction.

On the first line of the output file print the numerator of the winning probability. On the second line print its denominator. Both numerator and denominator must be printed without leading zeroes. Remember that the fraction must be irreducible.

2
4 6

1
3

//* @author:
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
static int oneNum[] = new int[65536];
static BigInteger arr[] = new BigInteger[20];
static int n;
static BigInteger list[] = new BigInteger[65536];

public static void main(String[] args) {
for(int i = 0; i < 16; i ++) {
for(int j = 1<< i; j < 1<< i+1; j ++) {
oneNum[j] = oneNum[j ^ (1<< i)] + 1;
}
}
///init over!
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
BigInteger ans1 = BigInteger.ZERO, ans2 = BigInteger.ONE;
for(int i = 0; i < n; i ++) {
arr[i] = scan.nextBigInteger();
ans2 = ans2.multiply(arr[i]).divide(ans2.gcd(arr[i]));
}

list[0] = BigInteger.ONE;
for(int i = 0; i < n; i ++) {
for(int j = 1<< i; j < 1<< i+1; j ++) {
list[j] = list[j^(1<< i)].multiply(arr[i]).divide(list[j^(1<< i)].gcd(arr[i]));
if((oneNum[j] & 1) == 1) {
} else {
ans1 = ans1.subtract(ans2.divide(list[j]));
}
}
}

BigInteger g = ans1.gcd(ans2);
ans1 = ans1.divide(g);
ans2 = ans2.divide(g);

System.out.println(ans1);
System.out.println(ans2);
}
}

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。