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を超えるため、高精度である必要がある
コードは次のとおりです.
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--;
}
}
}