yukicoder : No.3332 Consecutive Power Sum (Small)

Smallはすんなり。
https://yukicoder.me/problems/no/3332

問題

整数Nが与えられる。

としたとき、S(E,L,R)=Nとなる正整数(E,L,R)の組を列挙せよ。

なお、Nの上限は10^12である。

解法

• E=1の場合、S(E,L,R)=(R-L+1)*(R+L)/2=N なので、(R-L+1)*(R+L)=2*NとなるL,Rを求めればよい。
  • 2*Nの約数を求め、小さい方を(R-L+1)、大きい方を(R+L)としたとき、これを満たせるL,Rを答えればよい。
• Eが2以上の場合、愚直に累積和を計算していけばよい。

ll N;
__int128 S[1<<20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<array<ll,3>> ret;
	cin>>N;
	
	// E=1
	for(ll w=1;w*w<=2*N;w++) if(2*N%w==0&&w<2*N/w&&w%2!=2*N/w%2) ret.push_back({1LL,(2*N/w-w)/2+1,(2*N/w-w)/2+w});
	
	for(int e=2;e<=40;e++) {
		map<__int128,int> M;
		M[0]=0;
		for(ll a=1;a<=1<<20;a++) {
			__int128 v=1;
			FOR(i,e) v*=a;
			if(v>N) break;
			S[a]=S[a-1]+v;
			if(M.count(S[a]-N)) ret.push_back({e,M[S[a]-N]+1,a});
			M[S[a]]=a;
		}
	}
	
	
	sort(ALL(ret));
	cout<<ret.size()<<endl;
	FORR(r,ret) cout<<r[0]<<" "<<r[1]<<" "<<r[2]<<endl;
}

まとめ

なんか最近yukicoderの問題供給量が多いな。