---
title: 4B 硬幣樓梯
tags: solution
---

# B. 硬幣樓梯

### Binary Search

#include<iostream>
using namespace std;

int solve(int n) {
    long long l=1,r=n,m,s;
    while(l <= r) {
        m=l+((r-l)/2);
        s=(m*(m+1))/2;
        if(s<n) {
            if(n-s<m+1) return m;
            else l = m+1 ;
        }
        else if(s>n)
            r = m-1;
        else
            return m ;
    }
    return m;
}

int main() {
    long long t,n ;
    cin >> t;
    while(t--) {
        cin >> n;
        cout << solve(n) << endl;
    }
}

---

### Mathematic Solution
利用簡單的數學式逆推，就可以直接得出其數學公式解了。

$S=\dfrac{n(n+1)}{2}=\dfrac{1}{2}(n^2+n)\Rightarrow n^2+n-2S=0\Rightarrow n=\lfloor\dfrac{-1+\sqrt{1+8S}}{2}\rfloor$

# include <cstdio>
# include <cmath>

int main(){
    int T;
    int n;
    double dn;

    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        dn = n;
        printf("%d\n",(int)(floor((sqrt(1+8*dn)-1)/2)));
    }
}