http://icpc.ahu.edu.cn/OJ/Problem.aspx?id=514
LT在他还很小的时候就求出1/(1*2)+....+1/((n-1)*n)=1-1/n;
现在,在你还是很小的时候,你要求出:
1/(1*2*...*m)+...+1/(n*(n+1)*...*(n+m-1))=S
(m>1,n>0,n+m<=500)
Original | Transformed |
1 2
Original | Transformed |
1 2
先不考虑X和Y互质的事,即Y=(n+m-1)!
则第一个分子num[1]=Y/(m!),第二个分子num[2]=Y/(m+1)!*(1)....
推得num[s]=num[s-1]*(s-1)/(m+s-1)
X=num[1]+num[2]+......+num[n]
最后X=X/(gcd(X,Y))
Y=Y/(gcd(X,Y))
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
static BigInteger[] num=new BigInteger[505];
public static void main(String[] args)
{
int n,m;
BigInteger x=BigInteger.valueOf(0),y=BigInteger.valueOf(1),one=BigInteger.valueOf(1);
Scanner cin = new Scanner(new BufferedInputStream(System.in));
n=cin.nextInt();
m=cin.nextInt();
for(int i=1;i<(n+m);++i)
y=y.multiply(BigInteger.valueOf(i));
num[1]=one;
for(int i=1;i<=m;++i)
num[1]=num[1].multiply(BigInteger.valueOf(i));
num[1]=y.divide(num[1]);
for(int i=2;i<=n;++i)
{
num[i]=num[i-1].multiply(BigInteger.valueOf(i-1)).divide(BigInteger.valueOf(m+i-1));
}
for(int i=1;i<=n;++i)
x=x.add(num[i]);
System.out.println(x.divide(x.gcd(y)).toString());
System.out.println(y.divide(x.gcd(y)).toString());
}
}