HDFS（数学题）

题目连接：http://acm.tju.edu.cn/toj/showp.php?pid=4119

4119. HDFS

Time Limit: 5.0 Seconds Memory Limit: 5000K
Total Runs: 196 Accepted Runs: 70

In HDFS( Hadoop Distributed File System), each data may have a lot of copies in case of data lose.
This problem, every data has its own id, from 1 to n. To make things simple, each data has only two copies.
This time, the HDFS is cracked by some stupid reason. Fortunately, tmeteorj knows that there are actually 2 data lost by his keen intuition.
Now, it is your time to show your value of life. You should tell tmeteorj the id of lost data.

INPUT

First line, there will a number T(1≤T≤10), means the test case of this problem.
After this, each line is first a number n(1≤n≤5000000), means data id is from 1 to n. Then there will be 2(n-1) numbers means the id of data in health state.

OUTPUT

For each case, print the lost id of data. The smaller id is in the front of the bigger one.

Sample Input


3
4 1 1 2 3 4 4
4 1 2 3 1 2 4
4 2 3 4 2 3 1

Sample Output


2 3
3 4
1 4
题解： 一道简单的数学题 ，因为数据量十分大所以必须用O(n）的方法，算出所给的数的和记为S1 和所给的数的平方和记为S2 和数据没缺失前的所有数的和H1和数据没有缺失前的数的平方和H2
根据H1-S1 = x1+x2 和H2 - S2 = x1^2+x2^2 ;由数学公式推出x1和x2即可
下面是代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 using namespace std;
 5 int main()
 6 {
 7     int s1, s2, h1, h2, tm1, tm2;
 8     int t ;
 9     scanf("%d",&t);
10     while(t--)
11     {
12         int n;
13         scanf("%d",&n);
14         int tm = 2*n-2;
15         int p;
16         s1 = 0 ; s2 = 0 ; h1 = n*(n+1) ; h2 = 0 ;
17         for(int i = 0 ; i < tm ; i++)
18         {
19             scanf("%d",&p);
20             s1+=p;
21             s2+=p*p;
22         }
23         for(int i = 1 ; i <= n ; i++)
24         {
25             h2+=i*i+i*i;
26         }
27         tm1 = h1 - s1;
28         tm2 = h2 - s2;
29         int a , b ;
30         a = (sqrt(2*tm2 - tm1*tm1)+tm1)/2 ;
31         b = tm1 - a;
32         if(a<b)
33         printf("%d %d
",a , b);
34         else printf("%d %d
",b , a);
35     }
36     return 0;
37 }