第４問「ラディカル和」問題 解答

「ヒストリー和」問題の解法です。
問題文はこちら。
他の問題の解法は、第１問、第２問、第３問、第５問。

多数の m について、m²＋1 の素因数の積を求める問題です。
素朴にm²＋1 の素因数をひとつひとつ求めていたのでは時間がかかりすぎます。

ここでは篩を使った解法を紹介します。
同じアイデアは CodeIQ の過去の問題（数学の問題をプログラミングで解こう！「タンジェント・フラクション」問題解説｜CodeIQ MAGAZINE）でも紹介しました。

2 つの配列を用意しましょう。一方は m²＋1 で初期化し、もう一方は 1 で初期化します。

上側の配列を左端から見ていきます。1 でない値に遭遇したとき、その値 p は実は必ず素数です。
そしてそこから右に p おきに見た値は、すべて p の倍数となっています。
下図では、m = 1 の値である 2 おきに、上側の配列の値を 2 で割り尽くしていきます。
そして下側の配列に 2 をかけておきます。

さらに右隣を見ます。隣の値の 5 についても、同様に、配列の値を 5 で割り尽くしていきます。

その右隣も同様です。

このように配列をどんどん右に見ていくことで、非常に高速に m²＋1 の値を割っていけます。
こうして最終的に、下の配列に F(m²＋1) の値が並びます。

コード例は以下になります。

#include <iostream>
#include <vector>
using namespace std;
typedef int		s32;
typedef long long int	s64;

s64 G(s64 m) {
	// 2つの配列をそれぞれ1とn^2+1で初期化
	vector<s64> v(m + 1, 1), u(m + 1);
	for (s64 i = 1; i <= m; i++) u[i] = i * i + 1;
	for (s32 i = 1; i <= m; i++) {
		s64 p = u[i];
		if (p == 1) continue;
		for (s64 k = i; k <= m; k += p) {
			v[k] *= p;
			while (u[k] % p == 0) {
				u[k] /= p;
			}
		}
	}
	s64 answer = 0;
	for (s32 i = 1; i <= m; i++) answer += v[i];
	return answer;
}

int main(int argc, char *argv[])
{
	s64 m;
	cin >> m;
	cout << G(m) << endl;
}

これで ideone で実行時間 0.4 秒です。
あまり m の上限を緩くすると、愚直解＋コンパイル言語でちょっと待てばクリアできてしまうので、ギリギリ大きめの値にしました。