T2 WTP的大洗牌
服了标签没有题解
这道题我是蒟蒻，一分没骗
题面
时间限制: 10000ms（整整10秒！！！）
空间限制:
题目描述
与恶龙争斗过久，自身亦成为恶龙；当你凝视深渊，深渊也在凝视着你。
WTP 成神之后决定对他的不下进行一次大洗牌。
他总共有 n 对部下，每个部下有一个能力值。具体来说，第 i 对部下的能力值分别是 a_i , b_i 现在WTP想要将所有的部下全部除掉，换成一对自己的亲信 小T 和 小P 。
然而，WTP 的要求很严苛，他还要求 \prod_{1\le i\le n}(a_i^2+b_i^2) 在 模 2^{64} 意义下 与 x^2+y^2~(x,y\in\mathbb{Z},0\le x,y\le 2^{64}) 相等，其中 x,y 分别表示小 T 和小 P 的能力值。
现在你要找出一组满足条件的 x,y 。如果不存在解输出-1。
输入格式
第一行一个正整数 n ，表示 WTP 部下的对数。
第二行 n 个非负整数，第 i 个表示 a_i 。
第三行 n 个非负整数，第 i 个表示 $b_i$。
输出格式
如果不存在符合要求的解，输出-1。
否则，输入一行两个非负整数 x,y(x,y\in\mathbb{Z},0\le x,y<2^{64}) ，表示 小$T$ 和 小$P$ 的能力值。如果有多组解，输出任意即可。
样例
Input 1
3
1 1 1
1 2 3
Output 1
10 0
数据范围
对于 10% 的数据，满足 n = 1 。
对于另外 20% 的数据，满足 a_i=b_i 。
对于另外 30% 数据，满足 n=2 。
对于所有数据，满足 1\le n \le 5*10^5
该题正确算法不依赖于取模 2^{64}
题解及思路
骗分做法
输出-1
出题的预判了你的预判。
蒟蒻做法
哇这道题看不懂， 这个符号是什么东西。
-
先两行输入 a_i,b_i
-
把这些数根据操作累乘起来 $sum*=(a^2+b^2)$，
到界限就取余（ 2^64 好像爆 long~long 了，那就不写取余了！） -
从$0…\sqrt {sum}$遍历 $x$，那么$y=\sqrt{sum-x^2}$，再判断向下取整后是否 x^2+y^2==sum
#include <bits/stdc++.h>
using namespace std;
long long n,x[514191],y[514191],sum=1;
int main()
{
cin>>n;
if(n>100000)
{
cout<<-1;
return 0;
}
for(int i=1;i<=n;i++)
{
cin>>x[i];
}
for(int i=1;i<=n;i++)
{
cin>>y[i];
}
for(int i=1;i<=n;i++)
{
sum*=(x[i]*x[i]+y[i]*y[i]);
//sum%=18446744073709551616;
}
for(long long i=0;i*i<=sum;i++)
{
long long j=sqrt(sum-i);
if(i*i+j*j==sum)
{
cout<<j<<" "<<i;
return 0;
}
}
cout<<-1;
}
然后你会发现这道题直接爆掉了。
正解
-
看到题先别急着做，先纸上推导。
-
从 n=1 推起：$x^2+y^2=a_1^2+b_1^2$故当 n=1 时输入后可以直接输出 a_1,b_1 作为答案。
-
当 n=2 时：$x^2+y^2=(a_1^2+b_1^2)(a_2^2+b_2^2)$为了方便，记 a_1 为 a ，记 b_1 为 b ，记 a_2 为 c ，记 b_2 为 $d$。易得 $x^2+y^2=a^2c^2+a^2d^2+b^2c^2+b^2d^2$整理得$x^2+y^2=(a^2c^2+b^2d^2)+(a^2d^2+b^2c^2)$配方得$x^2+y^2=(ac+bd)^2-2abcd+(ad-bc)^2+2abcd$得$x^2+y^2=(ac+bd)^2+(ad-bc)^2$不妨使$x=(ac+bd)$ , $y=(ad-bc)$（结论）
-
当 n=3 时：做完同上的操作，不妨使已求得的 x 作为新的 $a$，$y$ 作为新的 $b$，新进入的 a_3 作为 c ，$b_3$作为 d ，再代入公式。
-
当 n>=3 时：依次类推。
-
-
所以说可以写代码了，n=1 写特判，直接输出；n>=2，代公式。
附代码
#include <bits/stdc++.h>
using namespace std;
int n;
unsigned long long a[514191],b[514191];
unsigned long long ans1,ans2;
int main()
{
cin>>n;
cin>>ans1;
for(int i=2;i<=n;i++)
cin>>a[i];
cin>>ans2;
for(int i=2;i<=n;i++)
cin>>b[i];
if(n==1)
{
cout<<ans1<<" "<<ans2;
return 0;
}
unsigned long long x,y,z;
for(int i=2;i<=n;i++)
{
x=a[i];
y=b[i];
z=ans1;
ans1=ans1*x+ans2*y;
ans2=z*y-ans2*x;
}
cout<<ans1<<" "<<ans2;
}
所以说，还有一个问题…
Tips：$unsigned$自动取模
$unsigned~long~long$：当$long~long$ 溢出时，可以清除溢出位。
因为$long~long$ 的能表示的数字正好是$2^{64}-1$，所以只要定义时加上$unsigned$就可以了。