AtCoder ABC #243 : G - Sqrt

Gは簡単なんだけどね…。
https://atcoder.jp/contests/abc243/tasks/abc243_g

問題

長さ1の整数列A=(X)が与えられる。
ここに以下の処理を10^100回行う。

• Aの末尾の要素をYとしたとき、1以上√Y以下の整数をAの末尾に追加する

解法

f(n) := Aの末尾がnであるとき、処理を繰り返してAの末尾が1になるまでの組み合わせ
とすると、

となるので、累積和を使えばO(n)でf(1)～f(n)まで埋められる。

ただXは上限10^18まで行くので、f(X)を直接求めるのは難しい。
そこでAの3要素目を総当たりすることを考える。
Aの3要素目はX^(1/4)程度になるので、総当たりできる。

Aの3要素目がnであるとき、2要素目は(n^2)～floor(√X)の値を取るので、(floor(√N)-n^2+1)*f(n)を計上しよう。

int T;
unsigned long long X;

ll pat[4010101];
ll sum[4010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	sum[1]=pat[1]=1;
	int sq=1;
	for(i=2;i<=3000000;i++) {
		if((sq+1)*(sq+1)<=i) sq++;
		pat[i]=sum[sq];
		sum[i]=sum[i-1]+pat[i];
	}
	
	
	cin>>T;
	while(T--) {
		cin>>X;
		unsigned long long sq=0;
		while((sq+10000)*(sq+10000)<=X) sq+=10000;
		while((sq+1)*(sq+1)<=X) sq++;
		
		ll ret=0;
		for(ll a=1;a<=3000000;a++) {
			if(a*a<=sq) ret+=(sq-a*a+1)*pat[a];
		}
		cout<<ret<<endl;
	}
}

まとめ

毎回大きな整数の平方根を取るの緊張する。