美国高中数学竞赛题,美国高中数学竞赛的数论题改写题目

来源：本站时间：2023-05-31 21:58:12 编辑：出国留学手机版

1. 题目

美国高中数学竞赛中的一道数论题目：

整数 $n\geq 2$。如果 $n$ 是质数，则 $S(n)=n$。如果 $n$ 不是质数，$S(n)$ 是所有因子 $d$ 的和，其中 $1

求比 $2019$ 小的全部循环质数的数量。

2. 题解

首先我们假设有一个循环质数 $n$，那么 $S(n)$ 必然不是质数。因为如果 $S(n)$ 是质数，那么 $S(S(n))=S(n)$，因此 $n$ 不是循环质数。

接着我们考虑，如果 $S(n)$ 是合数，那么 $S(S(n))$ 必然不是质数。因为 $S(n)$ 除了 $n$ 以外，还有其他因子，这些因子在 $S(S(n))$ 中都会被计算一遍，因此 $S(S(n))$ 也是合数。

所以，如果一个数 $n$ 满足 $S(n)$ 是合数，那么 $n$ 不可能是循环质数。

然后我们考虑，如果 $S(n)$ 中不包含 $2$，那么 $S(S(n))$ 必然是偶数。因为 $S(n)$ 中不包含 $2$，那么 $S(S(n))$ 就相当于计算了 $S(n)$ 的偶数倍，因此 $S(S(n))$ 是偶数。

因此，如果一个数 $n$ 满足 $S(n)$ 中不包含 $2$，那么 $n$ 不可能是循环质数。

综上所述，如果一个数 $n$ 是循环质数，那么 $S(n)$ 是质数，且 $S(n)$ 中包含 $2$。

然后我们可以枚举每一个 $n$，判断 $S(n)$ 是否为质数，且 $S(n)$ 中是否包含 $2$。如果是，我们就继续计算 $S(S(n))$，直到得到一个合数或者一个已经计算过的数（即出现循环）为止。如果最终得到的是一个质数，那么 $n$ 就是循环质数。

3. 代码

下面是判断一个数是否为质数的函数：


    bool is_prime(int n) {
        if (n<2) return false;
        for (int i=2; i*i<=n; i++) {
            if (n%i==0) return false;
        }
        return true;
    }

下面是计算 $S(n)$ 的函数：


    int s(int n) {
        int ans=1;
        for (int i=2; i
            if (n%i==0) ans+=i;
        }
        return ans;
    }

最后是判断一个数是否为循环质数的函数：


    bool is_circular(int n) {
        set visited;
        visited.insert(n);
        int sn=s(n);
        while (true) {
            if (!is_prime(sn) || sn==n) return false;
            if (visited.find(sn)!=visited.end()) return true;
            visited.insert(sn);
            sn=s(sn);
        }
    }

对于 $n=2$，$S(n)=1$，并不满足 $S(n)$ 包含 $2$ 的条件，因此不能算作循环质数。

对于 $2

代码如下：


    int ans=0;
    for (int n=3; n<2019; n++) {
        if (n%2==0) continue;
        int sn=s(n);
        if (sn%2==0) continue;
        if (!is_prime(sn)) continue;
        if (!is_circular(n)) continue;
        ans++;
    }
    cout << ans << endl;

答案为 $58$。