C++で(n^1 + n^2 + n^3 + n^4) mod 5の値を求める方法

問題概要

この問題では、ある整数 n が与えられ、(n¹ + n² + n³ + n⁴) mod 5 の値を求めることが課題となります。

具体例を見てみましょう。

入力：n = 5
出力：0

説明：

(51 + 52 + 53 + 54) mod 5
= (5 + 25 + 125 + 625) mod 5
= 780 mod 5 = 0

解法1：式を直接計算する方法

最もシンプルなアプローチは、与えられた n の値に対して式の値をそのまま計算し、その結果を5で割った余りを返す方法です。

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
int findMod5Val(int n){
   long long val = (long long)n + (long long)n*n + (long long)n*n*n + (long long)n*n*n*n;
   return val % 5;
}
int main(){
   int n = 12;
   cout<<"N = "<<n<<" のとき、(n^1 + n^2 + n^3 + n^4) % 5 の値は "<<findMod5Val(n);
   return 0;
}

出力：

N = 12 のとき、(n^1 + n^2 + n^3 + n^4) % 5 の値は 0

なお、n が大きくなると n⁴ の計算時に int 型ではオーバーフローが発生する恐れがあるため、long long 型を使用すると安全です。

解法2：数学的な変形を活用する方法

もうひとつの効率的な解法は、式を因数分解して一般化することです。

f(n) = n + n² + n³ + n⁴
f(n) = n × (1 + n + n² + n³)
f(n) = n × {(1 + n) + n²(1 + n)}
f(n) = n × (1 + n)(1 + n²)
f(n) = n × (n + 1)(n² + 1)

この因数分解された形から、n の値に応じて f(n) mod 5 は 0 または 4 のどちらかになることが導けます。

if(n % 5 == 1)
   f(n) % 5 = 4
else
   f(n) % 5 = 0

これは、n を5で割った余りが1になる場合を除き、因数である n、(n+1)、(n²+1) のいずれかが必ず5の倍数になるためです。

以下は、この解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;
int findMod5Val(int n){
   if(n % 5 == 1)
      return 4;
   return 0;
}
int main(){
   int n = 21;
   cout<<"N = "<<n<<" のとき、(n^1 + n^2 + n^3 + n^4) % 5 の値は "<<findMod5Val(n);
   return 0;
}

出力：

N = 21 のとき、(n^1 + n^2 + n^3 + n^4) % 5 の値は 4

まとめ

式を直接計算する方法でも正しい答えは得られますが、n が非常に大きい場合はオーバーフローのリスクがあります。因数分解の結果を利用した数学的アプローチであれば、O(1) の計算量で安全に答えを求められるため、大きな入力が想定される場面では特におすすめの解法です。