今天总算开始明白递归到底怎么用,然后做这个题的时候正常打表超时了，就试着用二分去做，没想到做出来了，very happy ^_^,

其实我之前还不会用也没用过二分

Position

题目描述

将1  开始的自然数按三角形排列，请问n  在第几行第几列？

1247⋯ 358 69 10  

输入

存在不超过10000  组样例，每行输入一个整数n(1≤n≤10 9 )  。

输出

每行输出一个样例的结果，为两个整数，分别表示行数和列数，中间用一个空格隔开，计数从1开始。

样例输入

1
10
100
1000000000

样例输出

1 1
4 4
14 9
44721 38440

#include<stdio.h>
#define _int __int64
int main()
{
    _int a[80000]={'\0'};
    for(_int i=1;(i*i-i)/2+1<=1000000000;i++)
    {
        a[i]=(i*i-i)/2+1;
    }
    _int n;
    while(scanf("%I64d",&n)!=EOF)
    {
        getchar();
        _int m=0,i=1,j=22000,k=44722;
        while(k-i>1)
        {
            if(n==a[i])
            {
                m=i;
                break;
            }
            if(n==a[j])
            {
                m=j;
                break;
            }
            if(n==a[k])
            {
                m=k;
                break;
            }
            //
            if(n>a[j])
            {
                i=j;
                j=(j+k)/2;
            }
            else
            {
                k=j;
                j=(i+j)/2;
            }
            //printf("a[%I64d]=%I64d a[%I64d]=%I64d a[%I64d]=%I64d n=%I64d\n",i,a[i],j,a[j],k,a[k],n);
            if(n==a[i])
            {
                m=i;
                break;
            }
            if(n==a[j])
            {
                m=j;
                break;
            }
            if(n==a[k])
            {
                m=k;
                break;
            }

        }
        if(m==i||m==j||m==k)
        {
            ;
        }
        else m=i;
        printf("%I64d %I64d\n",m,n-(m*m-m)/2);
    }
    return 0;
}