hdu 4762 && 2013 ACM/ICPC 长春网络赛解题报告

时间:2021-06-24 09:24:16

这次的答案是猜出来的,如果做得话应该是应该是一个几何概型的数学题;

答案就是:n/(m^(n-1));

具体的证明过程:

  1.首先枚举这M个点中的的两个端点,概率是:n*(n-1);

  2.假设这个蛋糕是个圆盘状的,圆面面积为1,然后为了满足题目的要求,这两个端点+圆心所组成的扇形的的面积应该小于1/m;

  3.然后对剩下的所有点都应该分布在这个扇形里面,加设扇形面积为x,则结果应该为:x^(n-2)在0-1/m中的积分,然后再乘以n*n-1;

n,m<=20.这牵扯到大数运算,为了简单起见就用了JAVA,这个题是小琪琪A掉的,不过发在这里,学习一下!

代码:

 import java.math.*;
import java.util.Scanner;
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t>0){
t-=1;
BigInteger m = sc.nextBigInteger();
BigInteger n = sc.nextBigInteger();
BigInteger pw=m.pow(n.intValue()-1);
System.out.println(n.divide(n.gcd(pw))+"/"+pw.divide(n.gcd(pw)));
} } }