给出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博客，格式可能有所偏差。 **