规定

• row：表示行号，从第0行开始
• col：表示列号，从第0列开始
• C(row, col)：组合数 n!/m!

杨辉三角的几条重要性质

• 每一行对称。
• 第row行、第col列的值 = C(row, col)。
• （a+b）的row次幂 的 展开式中的各项系数依次对应杨辉三角的row行中的每一项。
• 如果 C(row1, col1) = C(row2, col2)，那么如果row1 > row2，则col2 > col1。也就是一个数重复出现多次，那么第一次出现的位置的行号最小，列号最大。

题目

题解

x
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

using namespace std;

#define N 1000000000
//1e9

#define ll long long
// sn = n*(a1 + an) / 2;
#define pos(n, m) ((((n + 1) * n) >> 1) + m + 1)


ll C(int n, int m) { //计算组合数C(n, m)
    long long ans = 1;
    for (int i = 0; i < m; ++i) {
        ans *= (n - i);
        ans /= (i + 1);
    }
    return ans;
}

int main() {
    
    ll n;
    cin >> n;

    int max_col = 0;
    for (; C(max_col << 1, max_col) < n; ++max_col); //枚举列，找到 不小于n的 最小列的编号 
    
    for (int col = max_col; ~col; --col) { //枚举最大列 
    
        if (!col) { //枚举到第0列，是1 
            cout << "1" << endl;
            return 0; 
        }
        
        if (col == 1) { //特判，到了第一列, 那么就出现在第一列了 
            cout << pos(n, 1) << endl;
            return 0;
        }
        
        int row = col << 1; //获取行编号
        ll c = C(row, col); //当前列的最小元素 
        while (c < n) { //枚举该列的行 
            ++row;
            c = c * row / (row - col); // == C(row, col); 减小重复计算 
            //不能这样写  c = c / (row - col) * row;
        }
        
        //没有找到
        if (c > n) continue;
        //找到了
        cout << pos(row, col) << endl;
        return 0;
        
    } 

    return 0;
}