首页 > 其他 > 详细

孙膑庞涓猜数字

时间:2018-03-11 01:46:19      阅读:250      评论:0      收藏:0      [点我收藏+]

数学老师想好了两个自然数m,n,满足2≤m≤n≤100,他把m,n的和S告诉了甲,把m,n的积P告诉了乙,甲和乙都是非常聪明的学生,诚实可靠,进行了以下的对话:

甲:我不知道m,n的确切值,但我知道你也不知道。

乙:现在我知道了。

甲:现在我也知道了。

老师证实了甲和乙的表述都是有根据的,结论是正确的,求m,n的值。

这个推理题可以用程序来计算:

#include <bits/stdc++.h>
using namespace std;
const int N=100,N2=10000;
int num[N2+1];//质因数的个数

bool ok_s(int s){
    if(s>2*N)return false;
    for(int i=2;i<=N&&i<=s/2;i++){
        if(num[i*(s-i)]==2)return false;
    }
    return true;
}

bool ok_p(int p){
    if(p>N2)return false;
    int ans=0;
    for(int i=2;i<N&&i*i<=p;i++){
        if(p%i==0&&ok_s(i+p/i))ans++;
    }
    return ans==1;
}
bool ck(int s,int p){
    // 甲知道乙不知道,说明用 s 算出来的 p 都超过两个质因数
    if(!ok_s(s))return false;
    // 乙现在知道了,说明用 p 算出来的 s 只有一种情况是 用这个 s 算出来的 p 都超过两个质因数
    if(!ok_p(p))return false;
    // 现在甲知道了,说明用 s 算出来的 p 只有一种情况是算出来的 s 只有一种情况是 用这个 s 算出来的 p 都超过两个质因数
    int ans=0;
    for(int i=2;i<=N&&i<=s/2;i++){
        if(ok_p(i*(s-i)))ans++;
    }
    return ans==1;
}
void solve(){
    for(int i=2;i<=N;i++){
        for(int j=i;j<=N;j++){
            if(ck(i+j,i*j)){
                printf("%d %d\n", i, j);
            }
        }
    }
}
int main(){
    for(int i=2;i<=N;i++)if(!num[i]){
        for(int j=i;j<=N2;j+=i){
            int n=j;
            while(n%i==0){
                n/=i;
                num[j]++;
            }
        }
    }
    solve();
    return 0;
}

答案是4,13。

孙膑庞涓猜数字

原文:https://www.cnblogs.com/flipped/p/8542845.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!