京东2018校招C++工程师笔试题-编程题一

题目

描述

有一无限序列 arr 为 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5......
起始序号为 1,
给出一个数字 n,求此无限序列的第 n 个数是多少

输入

1 行, n, 1 <= n <= 1E+18

输出

输出 arr(n)

Example

Input

1
5

Output

1
3

题解

思路

• 假设此数列为一个对称矩阵的下三角
• 则必存在 i,j (1<=j<=i) 满足 n=i*(i-1)/2+j
• 整理得 ii-i+2 <= 2n = ii-i+2j -> i^2-i-2n+2<=0
• 最终,整数 i 的值为 (1+√(8*n-7))/2 取整
• 时间复杂度 O(1)

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main(){
    ll n,r;
    cin>>n;
    n<<=1;
    r=(1+sqrt(8*n-7))/2;
    cout<<r;
}