プロジェクトオイラー問375暫定解 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20375

問題の確認。
Let Sn be an integer sequence produced with the following pseudo-random number generator:

S0 = 290797
Sn+1 = (Sn)＾2 mod 50515093
Let A(i, j) be the minimum of the numbers Si, Si+1, ... , Sj for i ≤ j.
Let M(N) = ΣA(i, j) for 1 ≤ i ≤ j ≤ N.
We can verify that M(10) = 432256955 and M(10 000) = 3264567774119.

Find M(2 000 000 000).

とりあえずの解法。
計算時間24分の暫定解。
一分ルールは今のところ想像もつきません。
関数は最大でも50515093までの周期しか持たないことを利用して計算量を下げられる？

#include<stdio.h>
#include<map>
#include<iostream>

const int LIMIT=2000000000;
__int64 f(__int64 n){
	return (n*n)%50515093;
}

int main(){
	std::map<int,__int64> memo;
	std::map<int,__int64>::iterator it,it2;
	__int64 s=f(290797);
	memo[0]=0;
	memo[1]=s;
	__int64 ans=s;
	__int64 sum=s;
	for(int i=2;i<=LIMIT;i++){
		
		s=f(s);
		sum+=s;
		memo[i]=s;
		it=memo.lower_bound(i);
		it--;
		it2=it;
		it2--;
		if(i%1000000==0)std::cout<<i<<" "<<ans<<" "<<memo.size()<<"\n";
		while(it!=memo.begin()){
			__int64 p=(*it).first;
			__int64 p2=(*it2).first;
			__int64 n=(*it).second;
			if(n>=s){
				sum+=(p-p2)*(s-n);
				memo.erase(p);
				it=memo.lower_bound(p);
				it--;
				if(it==memo.begin())break;
				it2=it;
				it2--;
			}else{
				break;
			}
		}
		ans+=sum;
	}
	std::cout<<"ans"<<ans<<"\n";
}