プロジェクトオイラー問120 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20120
Problem 120 「自乗で割った余り」 †
(n-1)^a+(n+1)^a mod n^2でｎが決まりaが自然数の時この数式の最大値を考える。
3<=n<=1000の最大値の計を求めよ。

解法
aを適当に大きく式を展開したらn^2以上になる部分はmod計算に影響を与えません。
後は左辺展開後の残りのan+bの形だけみればすぐに答えが出ます。

#include <iostream>
#include <algorithm>
using namespace std;


int calc(int n){
	if(n%2==1){
 		return std::max(2,(n/2)*2*n);
	}else{
		return std::max(2,2*(n/2-1)*n);
	}
}

int main() {
	// your code goes here
	long long int ans=0;
 	for(int i=3;i<=1000;i++){
		ans+=calc(i);
	}
	cout<<ans<<"\n";
	return 0;
}