杨辉三角（算法）

题目

链接：https://www.lanqiao.cn/problems/1457/learning/

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 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。

运行限制

最大运行时间：1s
最大运行内存: 256M

思路

对杨辉三角形进行仔细观察可知道，其中有很多数是重复的，因此我们只需要记录其有效部分。具体规律如下图所示：

" class="lazyload placeholder" data-srcset="" srcset="https://pic1.zhimg.com/v2-cd38920285d125be80b3eb504052c550_b.webp" class="lazyload placeholder" data-srcset="" srcset="https://pic1.zhimg.com/v2-cd38920285d125be80b3eb504052c550_b.webp

还可以发现，对于同一行，列数越大对应的数值也越大。而且某一行的某一列的值为x，在列数不变的情况下，无论行数怎么变大都不会再出现比x小的数；同理再行数不变的情况下列数怎么变大也不会出现比x小的数。并且得知n小于等于10的0次方时，有效列数为0-16列。因此我们可以一列一列的考虑，由于随着行号的变大，数值时单调递增的，其知道了行号、列号对应的数值也就知道了，于是便可以二分行号，使用二分查找的方法来计算本题。

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;
    }

}