题目
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？
输入描述
输入一个整数 N。
输出描述
输出一个整数代表答案。
输入输出样例
示例 1
输入
输出
评测用例规模与约定
对于 20的评测用例，1≤N≤10； 对于所有评测用例，1≤N≤10000000000。
运行限制
思路
对杨辉三角形进行仔细观察可知道，其中有很多数是重复的，因此我们只需要记录其有效部分。具体规律如下图所示：
还可以发现，对于同一行，列数越大对应的数值也越大。而且某一行的某一列的值为x，在列数不变的情况下，无论行数怎么变大都不会再出现比x小的数；同理再行数不变的情况下列数怎么变大也不会出现比x小的数。并且得知n小于等于10的0次方时，有效列数为0-16列。因此我们可以一列一列的考虑，由于随着行号的变大，数值时单调递增的，其知道了行号、列号对应的数值也就知道了，于是便可以二分行号，使用二分查找的方法来计算本题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
for(int i=16;i>=0;i--){
if(pan(i,n)){
break;
}
}
scan.close();
}
public static boolean pan(int k,int n){
int left=k*2;
int right=Math.max(left,n);
while (left<right){
int mid=(left+right)/2;
long suan = suan(mid, k, n);
if(suan>=n){
right=mid;
}else {
left=mid+1;
}
}
long suan = suan(right, k, n);
if(suan==n){
System.out.println((long)(right+1)*right/2+k+1);
return true;
}
return false;
}
public static long suan(long mid,long k,int n){
long res=1L;
for(long i=mid,j=1;j<=k;j++,i--){
res=res*i/j;
if(res>n){
return res;
}
}
return res;
}
}
|
