Educational Codeforces Round 007. A

A. Infinite Sequence

문제

https://codeforces.com/contest/622/problem/A

 

문제요약

1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ... 의 규칙으로 나열되는 수열의 n번째 수는 얼마인가?

ex) 55번째는 10이다.

 

풀이

n(n+1)/2번째 수는 n이다. 그리고 그 이후 n+1개 수만큼 나열된다.

즉 55번째를 구하려면 45번째 이후부터 10개의 수가 각각 1, 2, 3, ~, 10임을 알고 10을 찾으면 된다.

수 범위가 10^14이므로 long long을 써주자

 

소스코드

#include <stdio.h>
typedef long long ll;
int main(){
    ll n, k;
    scanf("%lld",&n);
    for(k=1; k*(k+1)/2<n; ++k);
    printf("%lld ",n-k*(k-1)/2);
}