UVa 1646 - Edge Case(斐波那契+大整数)

给出n个点,求有多少组边(a,b)满足|a − b| ≡ 1 mod n。
设P[n]为边的个数,P[3]=4,P[4]=7。此后每项都是前两项的和。因为到10000项数很大,所以要用大整数,Java大整数比C++方便就用了。
原公式:
P[2n]=1+2n/1!+2n(2n-3)/2!+……+2n(n-1)!/n!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.math.*;
import java.util.*;
class Main
{
public static void main (String[] args)
{
BigInteger a[]=new BigInteger[10010];
a[3]=new BigInteger("4"),a[4]=new BigInteger("7");
for(int i=5;i<10010;++i)
a[i]=a[i-1].add(a[i-2]);
Scanner cin = new Scanner(System.in);
while (cin.hasNext()){
int n=cin.nextInt();
System.out.println(a[n]);
}
}
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。