前些天在班级群里看到一个笔试题：
从 1 到 100000 中任意拿掉两个数字，把剩下的 99998 个数顺序打乱，并且放入数组 A 中。要求只扫描一遍，把这两个数找出来；可以使用最多不超过 5 个局部变量，不能使用数组变量，并且不能改变原数组的值。
也想不到什么更好的解法，原解法是顺序扫一边求得所有数的乘积 (mul_res)、和 (sum_res)。用 (N!)/mul_res 得到两个数的乘积，1 到 100000 的和减去 sum_res 得到两个数之和。解这个方程得到两个数。关键是 N！太大了，C 会溢出。刚开始想想乘积每次模 100000，后来写了一下还是不对的，因为模 100000 中可能就出现了 0，后面全为 0 了。最后想到这么一个办法，不过中间 除法和比较多。也许有更快的解法。
//1 到 100 000
#include <iostream>
#include <math.h>
using namespace std;
#define N 100000
typedef long long LL;
LL a;
LL b;
LL vec[N];
int cnt;
LL MAX_MUL;
void Find(const LL* vec)
{
int sum=0;
LL mul=1;
LL Now=1;
for(int i=0;i<cnt;i++)
{
sum+=vec[i];
while(mul%vec[i]!=0)
mul*=(++Now);
mul/=vec[i];
}
while(Now<100000)
mul*=(++Now);
LL diff=((1+N)*N)/2-sum;
cout<<diff<<" "<<mul<<endl;
LL a=(diff+sqrt(diff*diff-4*mul))/2;
cout<<a<<" "<<diff-a<<endl;
}
int main()
{
srand(time(NULL));
a=(rand()%100000)+1;
b=(rand()%100000)+1;
cnt=0;
for(int i=1;i<=N;i++)
{
if(i!=a&&i!=b)
vec[cnt++]=i;
}
cout<<a<<" "<<b<<" "<<endl;
cout<<a+b<<" "<<a*b<<endl;
Find(vec);
}经熊师兄指点，上面的解法还是不对，如果 vec 前面刚好为比较大的素数，mul 就溢出了。正确的解法应该为求 x+y=B, x^2+y^2=A, 1-100000 的平方和可以用 double 存下来，然后减去 vec 里面的平方和就得到 x^2+y^2 的值。
void Find(const LL* vec)
{
double sum=0;
double square_sum=0;
for(int i=0;i<cnt;i++)
{
sum+=vec[i];
square_sum+=(vec[i]*vec[i]);
}
double diff=((1+N)*N)/2-sum;
double square_sum_diff=
((double)N*(N+1)*(2*(double)N+1))/6 - square_sum;
cout<<diff<<" "<<square_sum_diff<<endl;
a=(2*(diff)+sqrt(8*square_sum_diff-4*diff*diff))/4;
cout<<a<<" "<<diff-a<<endl;
}