题目描述
Polycarp has found a table having an infinite number of rows and columns. The rows are numbered from 1, starting from the topmost one. The columns are numbered from 1, starting from the leftmost one.
Initially, the table hasn’t been filled and Polycarp wants to fix it. He writes integers from 1 and so on to the table as follows.
The leftmost topmost cell of the table is filled with the number 1. Then he writes in the table all positive integers beginning from 2 sequentially using the following algorithm.
First, Polycarp selects the leftmost non-filled cell in the first row and fills it. Then, while the left neighbor of the last filled cell is filled, he goes down and fills the next cell. So he goes down until the last filled cell has a non-filled neighbor to the left (look at the vertical arrow going down in the figure above).
After that, he fills the cells from the right to the left until he stops at the first column (look at the horizontal row in the figure above). Then Polycarp selects the leftmost non-filled cell in the first row, goes down, and so on.
A friend of Polycarp has a favorite number k. He wants to know which cell will contain the number. Help him to find the indices of the row and the column, such that the intersection of the row and the column is the cell containing the number k.
Input
The first line contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.
Each test case consists of one line containing one integer k (1≤k≤109) which location must be found.
Output
For each test case, output in a separate line two integers r and c (r,c≥1) separated by spaces — the indices of the row and the column containing the cell filled by the number k, respectively.
样例输入
7
11
14
5
4
1
2
1000000000
样例输出
2 4
4 3
1 3
2 1
1 1
1 2
31623 14130
题意
数字从1开始按照图片中给定的顺序进行排列,给出一个数,求这个数在第几行第几列。
输出要求数的行和列。
思路
可以先通过开方的方式将其限定在第几行
如果这个数是某个数的平方,则可以直接确定其位置是在第一列的第几行
如果不是,由于开方函数是下取整,则可以确定其所在第几次排列
将这个数与当次排列中处于对角线位置的数(如1.3.7)进行比较,可以得出它是和对角线位置的数处于同一行还是同一列
进行简单的计算即可
C++ 代码
#include <iostream>
#include <math.h>
using namespace std;
typedef long long LL;
int t;
LL n;
int main()
{
cin>>t;
while(t--)
{
scanf("%lld",&n);
LL p=sqrt(n);
if(p*p==n)
{
printf("%lld 1",p);
}
else
{
if(n==p*(p+1)+1)
{
printf("%lld %lld",p+1,p+1);
}
else
{
if(n<p*(p+1)+1)
{
printf("%lld %lld",n-(p*p+1)+1,p+1);
}
else
{
printf("%lld %lld",p+1,(p+1)*(p+1)-n+1);
}
}
}
printf("\n");
}
return 0;
}