| by XianKa | No comments

【数论】一道神奇的数论题

随意写下两个正整数 2 < x, y < 99
A知道其乘积,B知道其和。

A:我不知道这两个数,但我确定B也不知道
B:我也不知道这两个数,但我确定A也不知道
A:我知道了
B:我知道了
问:这两个数是多少

先假设s=x+y,t=xy

  1. A第一句话首先表明了t肯定有大于一种合法的分解方法。
  2. A的第二句话说“B不知道”,说明了s \in [7,195],因为如果s=5则只能为2+3,其他数同理。
  3. B的第一句话证明了A第二句话的是正确的。
  4. B的第二句话确定“A不知道”,说明s=x+y无论写成什么形式,t=xy都不可能只有一种分解方法,也就是说s肯定不是两个质数的和。

到此位置可以得到一些数,这些数可能是s

11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 166 167 169 171 173 174 175 177 178 179 181 182 183 184 185 187 188 189 190 191 192 193 194 195

  1. 接着A说他知道了这两个数是什么。说明t=xy得到的s=x+y,这个t无论怎么分解,得到的x+y只有一组在上面求到的s集合中。

比如:

s x y t
11 2 9 18
11 3 8 24
11 4 7 28

由于A掌握有乘积t,所以他立刻能知道是哪两个数。到此,我们还不能完全知道这两个数是什么。

  1. 最后B说他知道了这两个数,说明s=x+y这个S只有一种拆法能满足条件。查表验证得到x=4,y=13
#include<bits/stdc++.h>
using namespace std;
int primes[202], cnt;
bool st[2002], s[202];
vector<pair<int,int> > t[202];
void get_primes(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; j < cnt && i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}
bool check(int x)
{
    int cnt = 0, res = 0;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0) 
        {
            if(x / i > 99) continue;
            if(!s[x / i + i]) cnt++;
            res ++;
            if(cnt > 1) return true;
        }
    }
    return false;
}
int checkT(int x)
{
    int res = 0;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0) 
        {
            if(x / i > 99) continue;
            res ++;
        }
    }
    return res;
}
int main()
{
    // s = x + y, t = x * y
    get_primes(100);
    for(int i = 0; i < cnt; i++)
        for(int j = i + 1; j < cnt ; j++)
            s[primes[i] + primes[j]] = 1; // s which is impossible
    //for(int i = 7; i <= 195; i++) if(!s[i]) printf("%d ", i);
    for(int i = 7; i <= 195; i++)
    {
        if(!s[i])
        {
            for(int x = 2; x <= i / 2; x ++)
            {
                int y = i - x; // for every x + y
                if(y > 99 || x == y) continue;
                if(checkT(x * y) == 1) 
                {
                    t[i].clear();
                    break;
                }
                if(!check(x * y)) // if has only x + y made x * y
                {
                    t[i].push_back({x,y}); // this t is possible
                }
            }
        }
    }
    for(int i = 7; i <= 195; i++)
    {
        if(t[i].size() == 1) 
        {
            //printf("%d\n", i);
            printf("%d %d\n", t[i][0].first, t[i][0].second);
            // for(auto j : t[i])
            // {
            //     printf("%d %d\n", j.first, j.second);
            // }
        }
    }
}

发表评论