C++で数のPoliteness（礼儀正しさ）を求める方法【素因数分解で効率化】

この記事では、正の整数Nが与えられたときに、その数の「Politeness（礼儀正しさ）」をC++で求める方法を解説します。

Polite Number（礼儀正しい数）とは？

Polite Numberとは、2つ以上の連続する整数の和として表すことができる数のことです。

数のPolitenessは、その数を連続する整数の和で表現できる方法の総数として定義されます。

例で問題を理解する

入力：

n = 5

出力：

1

説明：
2 + 3 = 5 が唯一の連続する整数の和であり、これ以外の表し方は存在しないため、答えは1になります。

解法アプローチ

1. シンプルな解法（全探索）

最も単純なアプローチは、N以下のすべての連続する整数列を順番に調べ、その合計がNと一致するかを確認する方法です。一致するたびにカウントを増やしていき、最終的なカウントがその数のPolitenessとなります。ただし、この方法は計算量が膨大になり、大きな数に対しては非効率です。

2. 効率的な解法（素因数分解を利用）

より効率的なのが、素因数分解を使った解法です。数のPolitenessは「奇数の約数の個数 − 1」に等しく、次の公式で求められます。

数Nが N = a^x × b^y × c^z … と素因数分解できるとき、

Politeness = [(x + 1) × (y + 1) × (z + 1) …] − 1

なお、2のべき乗の因子はPolitenessに影響しないため、計算の前にあらかじめ取り除いておきます。

解法の実装例

#include <iostream>
using namespace std;

int calcPolitenessNumber(int n){
    int politeness = 1;
    // まず2の因子をすべて取り除く
    while (n % 2 == 0)
        n /= 2;
    // 奇数の素因数ごとに指数を数える
    for (int i = 3; i * i <= n; i += 2) {
        int divCount = 0;
        while (n % i == 0) {
            n /= i;
            ++divCount;
        }
        politeness *= divCount + 1;
    }
    // 残ったnが2より大きい場合、それは指数1の奇数の素因数
    if (n > 2)
        politeness *= 2;
    return (politeness - 1);
}

int main(){
    int n = 13;
    cout<<"Politeness of "<<n<<" is "<<calcPolitenessNumber(n);
    return 0;
}

出力

Politeness of 13 is 1

まとめ

このコードでは、まず2の因子を除去し、その後3から順に奇数の素因数で割り切れる回数（指数）を数えながら、(指数 + 1) を掛け合わせてPolitenessを計算しています。最後に1を引くのは、「その数自身（1項だけの和）」という表現を除外するためです。全体の計算量はO(√N)に抑えられ、全探索方式と比べてはるかに高速に動作します。