鬼谷子猜数

很久之前写的，搬过来。

一个与OI本身并木有什么联系的问题，只是感觉很有趣而且验证过程用到了计算机（主要是懒得手算），便花一点点时间来写一下。

问题

一天，鬼谷子随意从2-99中选取了两个数。他把这两个数的和告诉了庞涓，把这两个数的乘积告诉了孙膑。但孙膑和庞涓彼此不知道对方得到的数。第二天，庞涓很有自信的对孙膑说：“虽然我不知道这两个数是什么，但我知道你一定也不知道。”随后，孙膑说：“那我知道了。”接着庞涓说：“那我也知道了”。

请问这两个数是什么？

解法

看似很无厘头的对话，但这个问题确实有解。世界真奇妙。

接下来让咱们一句句分析：

• 庞涓：“我不知道这两个数是什么”

这句话……跳过。其实它也不是没有蕴含信息（这句话表明庞涓得到的数不是2、3或197、198），但信息实在太少了。不管它就行了。

• 庞涓：“但我知道你不知道”

翻译一下就是，庞涓肯定自己的数不存在一种分解使得它们的乘积告诉孙膑之后他能立马猜出这两个数。

首先第一步，我们可以反向思考，孙膑得到哪些数之后，能立马猜出来？

一种可能是它是两个质数的乘积，原因显而易见。另一种是这个数是53与另外一个数的乘积，因为这样的乘积也都只有一种分法（53\(\times ?\)），毕竟只要再分给53一个因子第一个乘数就超范围了。

整理一下，庞涓拿到的数不会大于54（因为保不准鬼谷子想到的数就有53），也不会能等于两个质数之和。那……都有哪些数？

上代码。其中check函数为判断是否为质数的函数。

for(int i=4;i<=54;i++){
	bool ok=true;
	for(int j=2;j<=i/2;j++)
		if(check(j)&&check(i-j)){ok=false;break;}
	if(ok)printf("%d ",i);
}

输出：11 17 23 27 29 35 37 41 47 51 53

• 孙膑：“那我知道了”

没错我们的懂王听完庞涓的话之后懂了。这句话说明什么？首先要明确一点，既然到这一步为止我们已经推断出庞涓手上可能的数有哪些，那么机智过人的孙膑肯定也早就得出了这个数列。而他懂了，说明他手上的数分解后所有可能的两数之和有且只有一个在上述集合之中。

很绕，非常绕。但确实求得出来有哪些可能的值。代码中A数组记录了上面得到的11个数，下标从1开始。

for(int i=1;i<=11;i++){
	for(int j=2;j<=A[i]/2;j++){
		num[j*(A[i]-j)]++;
	}
}
for(int i=1;i<1000;i++)if(num[i]==1)printf("%d ",i);

输出（后面的输出不重要）18 24 28 50 52 54 76 92 ......

• 庞统：“那我也知道了”

没错我们的另一个懂王听完孙膑的话之后也懂了（tmd就你们最懂）。这说明什么？套用刚才的分析方法，我们可以知道，庞统应该也得到上面我们输出的那一长串数了。而庞统现在懂了，说明什么？说明他手上的数只有一种方法可以拆分为两个数使得这两个数的乘积在上面的那个集合之中。接下来的事情不就好办了吗，枚举就行了啊……

代码是在上一步的基础上完成的。

for(int i=1;i<=11;i++){
	for(int j=2;j<=A[i]/2;j++){
		num[j*(A[i]-j)]++;//代表此乘积的方案数加一 
		fr[j*(A[i]-j)]=i;//记录这个乘积是由哪个和转移过来的 
	}
}
for(int i=1;i<1000;i++){
	if(num[i]==1){//如果当前i在上一步得到的那个奇怪的集合中 
		use[fr[i]]++;//记录这个和可能的种数 
		one[fr[i]]=i;//顺便记录一下从哪里来的 
	}
}
for(int i=1;i<=11;i++){
	if(use[i]==1){//如果这个和只有一种分解方法说明他是正解 
		printf("%d %d",A[i],one[i]);
		//注意此时输出的是鬼谷子想的两个数的和与积 
	}
}

输出17 52

没错，只有一种可能。

• 最后一步

问题变成了已知两个数的和与两个数的积，求这两个数。这就有点侮辱人了对吧。显然可以求出这两个数分别是13和4。然后就完了。

当时是在一个奇怪的CSP-J初赛中做到的这道题，当时顿时怀疑人生（好家伙入门组都这么难那还玩个鬼），下来之后看网上各种题解，发现其中使用各种各样的分析技巧和数论知识本蒟蒻都不会，便想到能否用其它方法来搞定这道题。于是，学过\(10^{-43}\)秒信竞的我决定秉承着“暴力出奇迹打表拿省一”的精神暴力枚举（其实数据规模也不大），没想到真的枚举出来了。特写此文纪念。

原创不易哦（你应该知道我想说啥吧）。