趣味思考题：请通过编程求解如下孙膑和庞涓问题。

Question

**********
趣味思考题：请通过编程求解如下孙膑和庞涓问题。
庞涓拿到两个整数（这个整数均在2到99之间）之和，孙膑拿到这两个整数之积。下面是一段很有趣的对话。
庞涓说：我不知道这两个整数是多少，但我肯定你也不知道。
孙膑说：我本来不知道这两个数是多少。但既然你这么说，那我现在知道了。
庞涓说：哦，那我也知道了。
要求输出所有可能的结果，包括这两个整数、这两个整数之和以及这两个整数之积。
**********

Answer 1

import java.util.*;
 
/**
 * 2<=a,b<=100 <br>
 * S knows a+b <br>
 * P knows a*b <br>
 * S: I don't know a nor b, and I know you don't know either <br>
 * P: now I know <br>
 * S: now I know <br>
 * What are a and b?
 * 改編自 Owen 的程式
 */
public class SumProd {
    private static final int BOUND = 100;
    static boolean[] arBoIsValid = new boolean[BOUND * 2 + 1];
 
    public static void main(String arg[]) {
        final int BOUND_DOUBLED = BOUND + BOUND;
        for (int i = 4; i <= BOUND_DOUBLED; ++i) {
            arBoIsValid[i] = isValidSum(i);
        }
        for (int i = 4; i <= BOUND_DOUBLED; ++i) {
            if (arBoIsValid[i]) {
                int bound2 = i / 2, count = 0, tmp = 0;
                for (int j = 2; j <= bound2; ++j) {
                    if (isValidProduct(j, i - j) && isValidProduct(i - j, j)) {
                        if (++count <= 1) {
                            tmp = j;
                        }
                        else {
                            break;
                        }
                    }
                }
                //YoShi 說: 現在我也知道了!
                if (count == 1) {
                    System.out.println("tmp: " + tmp + ", " + (i - tmp));
                }
            }
        }
    }
 
    static boolean isOneWay(int a, int b) {
        for (int i = 2; i * i <= a; i++) {
            if (a % i == 0) {
                return b * i > BOUND; // 如果 b*i > BOUND，接下來也是
            }
        }
        return true;
    }
 
    //YoShi 說:我不知道這兩個數是多少,但我肯定你也不知道
    static boolean isValidSum(int n) {
        int bound = n / 2;
        for (int i = 2; i <= bound; i++) {
            if ( (n - i) <= BOUND && isOneWay(i, n - i) && isOneWay(n - i, i)) {
                return false; // YoShi 不能確定 Popcorny 不知道
            }
        }
        return true;
    }
 
    //Popcorny 說:我本來是不知道的,但是現在我知道了
    static boolean isValidProduct(int a, int b) {
        for (int i = 2; i * i <= a && b * i <= BOUND; i++) {
            if (a % i == 0) {
                if (arBoIsValid[a / i + b * i]) {
                    return false; //Popcorny 沒法確定
                }
                if (b * a / i <= BOUND && arBoIsValid[i + b * a / i]) {
                    return false;
                }
            }
        }
        return true;
    }
 
}
网上copy版，没有分析，答案是 4，13

Answer 2

所有的可能结果
public class test {
 
    public static void main(String[] args) {
        
        int i;
        int j;
        
        for (i = 2; i < 100; i++) {
            for(j=2;j<100;j++){
                int s=i+j;
                int t=i*j;
                System.out.println(" "+i+" "+j+" "+s+" "+t);
            }
    
        }
    }
}

Answer 3

假设：和为s，积为p，两个整数为a和b，其中s=a+b, p=a*b，称其为一对第1步：我不知道这两个整数是多少，但我肯定你也不知道。
这说明：
1、我不知道：s至少是两对整数的和，如果仅有一对的话，即a+b=s，那么“我”就知道这两个数是什么了，如5。
2、我肯定你也不知道：对于所有相加等于s的两个整数，他们的乘积p，至少有两对整数的乘积与p相等，同上，如果只有一对整数的乘积等于p，那么“你”就肯定知道这两个数了。
换句话说，这两个数不能都是质数
对于和为s的所有整数对，都要满足2，这就是“我肯定”的意思，因为只要有一对全部都是质数的话，“我”就不能“肯定”了。
所以，找到和为s，积为p，但不同时为质数的所有整数对
结果：和为11,17,23,27,29,35,37,41,47,51,53的整数满足条件
第2步：我本来不知道这两个数是多少。但既然你这么说，那我现在知道了。
这说明：
1、对于乘积为p的所有整数对，至少有一对他们的和是第1步结果之一
2、“我现在知道”说明对于乘积为p的整数对中，只有一对的和是第1步结果之一，如果不止一对的话，“我”还是不能确定。
所以：对于第1步结果中所有可能的整数对，相乘得到p，再统计所有乘积为p的整数对的和在第1步结果中出现的次数，出现次数为1的即为结果。
结果：整数对为4,13，他们和是s=17，他们的乘积为p=52
“那我也知道了”是废话。还有不明白的提出来，继续讨论。
程序见下

Answer 4

import java.util.*;public class FindOut { static int MIN = 2;
static int MAX = 99;
    static boolean[] available = new boolean[(MAX+MIN+1) * 2]; public static void main(String[] args) { // 假设：和为s，积为p，两个整数为a和b，其中s=a+b, p=a*b，称其为一对 // 第1步：我不知道这两个整数是多少，但我肯定你也不知道。
// 这说明：
// 1、我不知道：s至少是两对整数的和，如果仅有一对的话，即a+b=s，那么“我”就知道这两个数是什么了，如5。
// 2、我肯定你也不知道：对于所有相加等于s的两个整数，他们的乘积p，至少有两对整数的乘积与p相等，同上，如果只有一对整数的乘积等于p，那么“你”就肯定知道这两个数了。
// 换句话说，这两个数不能都是质数
// 对于和为s的所有整数对，都要满足2，这就是“我肯定”的意思，因为只要有一对全部都是质数的话，“我”就不能“肯定”了。
// 所以，找到和为s，积为p，但不同时为质数的所有整数对
// 结果：和为11,17,23,27,29,35,37,41,47,51,53的整数满足条件
loop1: for (int s=MIN*2; s<=MAX*2; s++) {
available[s]  = false;
Vector<IntPair> v = getAddFactors(s);
int len = v.size();
if (len < 2) {
continue loop1;
}
for (int i=0; i<len; i++) {
IntPair ip = v.get(i);
if (isPrimePair(ip)) {
continue loop1;
}
}
available[s]  = true;
} // 第2步：我本来不知道这两个数是多少。但既然你这么说，那我现在知道了。
// 这说明：
// 1、对于乘积为p的所有整数对，至少有一对他们的和是第1步结果之一
// 2、“我现在知道”说明对于乘积为p的整数对中，只有一对的和是第1步结果之一，如果不止一对的话，“我”还是不能确定。
// 所以：对于第1步结果中所有可能的整数对，相乘得到p，再统计所有乘积为p的整数对的和在第1步结果中出现的次数，，出现次数为1的即为结果。
// 结果：整数对为4,13，他们和是s=17，他们的乘积为p=52
for (int s=MIN*2; s<=MAX*2; s++) {
if (available[s]) {
Vector<IntPair> v = getAddFactors(s);
int index = indexOfAvailableSum(v);
if (0 <= index) {
IntPair ip = v.get(index);
System.out.println("Result is: " + ip.l + "," + ip.r + "  and sum=" + s + ", product=" + ip.l*ip.r);
}
}
}
// “那我也知道了”是废话。
} static Vector<IntPair> getAddFactors(int sum) {
Vector<IntPair> v = new Vector<IntPair>();
int max = Math.min((int)((sum+1)/2), MAX);
for (int i=MIN; i<=max; i++) {
int j = sum - i;
if ((i <= j) && (j<=MAX)) {
v.add(new IntPair(i, j));
}
}
return v;
} static boolean isPrimePair(IntPair ip) {
        for (int i=2; (i*i)<=ip.l; i++) {
            if (ip.l % i == 0) {
                if ( (ip.r*i)<=MAX ) {
                 return false;
                }
            }
        }
        for (int i=2; (i*i)<=ip.r; i++) {
            if (ip.r % i == 0) {
                if ( (ip.l*i)<=MAX ) {
                 return false;
                }
            }
        }
        return true;
    }    static int indexOfAvailableSum(Vector<IntPair> v) {
     int result = -1;
int len = v.size();
     int[] count = new int[len];
for (int i=0; i<len; i++) {
count[i] = 0;
IntPair ip = v.get(i);
int p = ip.l * ip.r;
        for (int j=2; (j*j)<=p; j++) {
            if ((p%j == 0) && (p/j <= MAX)) {
                if (available[j + p/j]) {
                 count[i]++;
                }
            }
        }
} int count1 = 0;
for (int i=0; i<len; i++) {
if (1 == count[i]) {
count1++;
}
} if (1 == count1) {
for (int i=0; i<len; i++) {
if (1 == count[i]) {
result = i;
}
}
} return result;
    }
}class IntPair {
int l;
int r;
IntPair(int i1, int i2) {
l = i1;
r = i2;
}
}