Lý thuyết

Dễ dàng nhìn thấy dãy A có dạng:

1: 1

2: 1 2

3: 1 2 3

4: 1 2 3 4

5: 1 2 3 4 5

...

N : 1 2 3 4 5 6 ... N

 Đến đây ta chỉ cần chạy trâu từ i = 1 đến vô tận và trừ n liên tục đi cho đến khi n $\leq$ 0

ĐPT:O(T.$\sqrt{N}$)

Code

#include <bits/stdc++.h>
using namespace std;

int q;
long long n;
int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(nullptr); cout.tie(nullptr);
    cin >>q;
    while (q--){
        cin >>n;
        long long tmp = sqrt(2 * n);
        if (tmp * (tmp + 1) / 2 > n) --tmp;
        if (tmp * (tmp + 1) / 2 == n) cout <<tmp;
            else cout <<n - (tmp * (tmp + 1) / 2);
        cout <<'\n';
    }
}

@zukako

var i, t: longint;
    tmp, n, s: int64;
begin readln(t);
    for i:= 1 to t do begin readln(n); tmp:= trunc(sqrt(2 * n));
        if tmp * (tmp + 1) div 2 > n then dec(tmp);
        if tmp * (tmp + 1) div 2 = n then writeln(tmp)
            else writeln(n - (tmp * (tmp + 1) div 2)); end;
end.