C++で算術数（約数の平均が整数になる数）を判定する方法

算術数とは

算術数（Arithmetic Number）とは、その数のすべての正の約数の平均（相加平均）が整数になる数のことです。つまり、ある数 n について「約数の総和 ÷ 約数の個数」が割り切れる場合、その n は算術数であると定義されます。

具体例で確認してみましょう。

入力 : n = 6
出力 : YES
説明 :
約数は 1, 2, 3, 6
約数の総和 = 1 + 2 + 3 + 6 = 12
約数の個数 = 4
約数の総和 ÷ 約数の個数 = 12 / 4 = 3（整数なので算術数）

なお、素数 p の場合、約数は 1 と p の2つだけなので平均は (1 + p) / 2 となります。p が奇素数であれば必ず整数になるため、すべての奇素数は算術数であることも分かります。

判定アルゴリズム

算術数かどうかの判定は、以下の手順で行います。

1. 約数の総和を計算し、変数 sum に格納する。
2. 約数の総個数を求める。
3. 約数の総和を約数の総個数で割った余りが 0 になるかどうかを確認する。
4. 余りが 0 であれば「YES」を出力し、そうでなければ「NO」を出力する。

C++での実装例

以下の実装では、エラトステネスの篩を利用して約数の個数を効率よく求め、約数の総和は素因数分解に基づく公式（約数関数）で計算しています。

#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]);
int countDivisors(int n);
int sumofFactors(int n);

int main(){
    int n = 46;
    int divcount = countDivisors(n);
    int divsum = sumofFactors(n);
    if(divsum % divcount == 0){
        cout << "YES";
    }
    else
        cout << "NO";
    return 0;
}

// エラトステネスの篩で素数表と素数の平方表を作成
void SieveOfEratosthenes(int n, bool prime[], bool primesquare[], int a[]){
    for (int i = 2; i <= n; i++)
        prime[i] = true;
    for (int i = 0; i <= (n * n + 1); i++)
        primesquare[i] = false;
    prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
    int j = 0;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            a[j] = p;
            primesquare[p * p] = true;
            j++;
        }
    }
}

// 約数の個数を求める関数
int countDivisors(int n){
    if (n == 1)
        return 1;
    bool prime[n + 1], primesquare[n * n + 1];
    int a[n];
    SieveOfEratosthenes(n, prime, primesquare, a);
    int ans = 1;
    for (int i = 0;; i++) {
        if (a[i] * a[i] * a[i] > n)
            break;
        int cnt = 1;
        while (n % a[i] == 0){
            n = n / a[i];
            cnt = cnt + 1;
        }
        ans = ans * cnt;
    }
    if (prime[n])
        ans = ans * 2;
    else if (primesquare[n])
        ans = ans * 3;
    else if (n != 1)
        ans = ans * 4;
    return ans;
}

// 約数の総和を求める関数
int sumofFactors(int n){
    int res = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        int count = 0, curr_sum = 1;
        int curr_term = 1;
        while (n % i == 0) {
            count++;
            n = n / i;
            curr_term *= i;
            curr_sum += curr_term;
        }
        res *= curr_sum;
    }
    if (n >= 2)
        res *= (1 + n);
    return res;
}

実行結果

YES

このプログラムでは n = 46 を判定しています。46 の約数は 1, 2, 23, 46 の4つで、総和は 72。72 ÷ 4 = 18 となり平均が整数になるため、「YES」が出力されます。

まとめ

算術数の判定は「約数の総和が約数の個数で割り切れるか」というシンプルな条件で実現できます。約数の個数と総和を効率的に計算することで、大きな数に対しても高速に判定が可能です。競技プログラミングや数論の学習において、約数関数やエラトステネスの篩と組み合わせて活用できるテーマです。