蓝桥杯杨辉三角一个数出现第一次排第几个

题目

讲解

前置知识

这里我们用到了杨辉三角的基本性质

• 1，杨辉三角是对称的，一个数第一次出现必定出现在中轴线的左边。

• 2，每一个斜线，第一个元素的下标a为2i（i从0开始），上标b为第i个斜线。这里的a正好比行号少1。

  讲解

• 我们这里遍历每条斜线，利用二分找到所需要查找的数n。

• 这里因为这里的a(也就是l)比行数正好少1，b也比列数少1。所以这里是相当于最后求得的行数为l+1，列数就为第几个斜线+1，最后求排在第几个，就是前面的（不算本行）是等差数列公差为1，用高斯算法就行了，然后再加上本行的列数就Ok了。
  

• 为什么要从第16行开始而不是其他行呢？

  因为显然C（32,16）< 1e9，而C（34,17）> 1e9，因此我们可以对前16行进行枚举。

注意：我们最后要从第十六个直线开始判断。首先对于左半边杨辉三角来说，每行最大的数一定出现在该行末尾，同时它也是该数最早出现的位置。

源码

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define endl "\n"

const int N = 1e5 + 10;

const int M = 110;

int n;

LL c(int a, int b)
{
    LL res = 1;
    for (int i = a, j = 1; j <= b; i --, j ++)
    {
        res = res * i / j;
        if (res > n) return res;
    }
    return res;
}

bool check(int x)
{
    int l = x * 2, r = max(n, l);
    while(l < r)
    {
        int mid = l + r >> 1;
        if(n <= c(mid, x)) r = mid;
        else l = mid + 1;
    }

    if (c(l, x) == n)
    {
        cout << 1ll* (l + 1) * l / 2 + x + 1 << endl;
        return true;
    }
    else return false;

}

void solve()
{

    cin >> n;
    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }
    for (int i = 16; i >= 0; i -- )
    {
        if (check(i)) break;
    }

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}