HDU 4762 Cut the Cake(確率)

1032 ワード

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4762
 
タイトル:
原型ケーキをm部の扇形に分け、n個のイチゴをちょうどその中の1部に
 
分析:
n種の選択があるためにまず1つを取り出し,残りのn−1個のイチゴはその極角[0360/m]の範囲内であった.
1つの確率は1/mであり、n-1つの確率は1/m^(n-1)である.
従って、総確率はn/m^(n-1)であり、20^20がlonglongを超えるため、高精度である必要がある
 
コードは次のとおりです.
//package fuck;

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static BigInteger gcd(BigInteger a,BigInteger b){
		if(!b.equals(BigInteger.ZERO)) return gcd(b,a.mod(b));
		return a;
	}
    public static void main(String args[]){  
        Scanner cin=new Scanner(System.in);  
        int t =  cin.nextInt();
        while(t>0){
        	int m = cin.nextInt();
        	int n = cin.nextInt();
        	BigInteger N = BigInteger.valueOf(n);
        	BigInteger M = BigInteger.valueOf(m).pow(n-1);
        	BigInteger tmp = gcd(N,M);
        	System.out.println(N.divide(tmp)+"/"+M.divide(tmp));
        	t--;
        }
    }  
}