|
||||||||||
Pair Sum and Perfect SquareTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 1989 Accepted Submission(s): 540 Problem Description A permutation of $n$ elements is an array of $n$ numbers from $1$ to $n$ such that each number occurs exactly one times in it. Given a permutation $p$ of $n$ elements, there are $Q$ queries to be made. Each query provides two integers $L$ and $R (1 ≤ L ≤ R ≤ n)$, asking how many pairs $(i, j)$ satisfy $L \leq i < j \leq R$ and $p_i + p_j$ is a square number. A square number is the product of some integer with itself. For example, $9$ is a square number, since it can be written as $3^2$. Input The first line contains an integer $T (T\leq 5)$, representing the number of test cases. For each test case, the input consists of $Q+3$ lines: The first line contains an integer $n (1 \leq n \leq 10^5)$, representing the length of permutation $p$. The second line contains $n$ integers $p_1, p_2, ..., p_n (1 \leq p_i \leq n)$, representing the elements of permutation $p$. The third line contains an integer $Q (1 \leq Q \leq 10^5)$, indicating the number of queries. The next $Q$ lines each contain two integers $L$ and $R (1 \leq L \leq R \leq n)$, representing the range of each query. Output For each query in each test case, output one line containing an integer, representing the answer. Sample Input
Sample Output
Source | ||||||||||
|