AtCoder ARC #135 : E - Sequence of Multiples

なるほど…。
https://atcoder.jp/contests/arc135/tasks/arc135_e

問題

整数N,Xが与えられる。

• A[1]=X
• A[i]=A[i-1]より大きいiの倍数の最小値

として構築される数列Aの、先頭N要素の総和を求めよ。

解法

B[i]=A[i]/iとする。
B[i+1]-B[i]=1-ceil(B[i]/(i+1))は単調減少になるし、そのバリエーションは少ない。

そこで、B[i+1]-B[i]が等しいiの区間について、まとめてB[i]*iの総和を計算しよう。
この手順は2つの等差数列の積の総和だが、連続する整数の1乗和・2乗和の公式を使えば区間あたりO(1)で求められる。
また、B[i+1]-B[i]が等しい区間はO(N^(1/3))通り程度なので、何とか間に合う。

int T;
ll N,X;
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X;
		
		ll cur=1;
		ll ret=0;
		while(cur<=N) {
			ll d=(X+cur)/(cur+1)-1;
			
			if(d==0) {
				ll a=(cur+N)%mo*((N-cur+1)%mo)%mo*((mo+1)/2)%mo;
				(ret+=X%mo*a)%=mo;
				break;
			}
			
			ll p=X+(cur-1)*d;
			ll q=2*d;
			
			
			ll a=min(N,(p+q-1)/q-1);
			
			ll b=(cur+a)%mo*((a-cur+1)%mo)%mo*((mo+1)/2)%mo;
			(ret+=(X%mo)*b)%=mo;
			ll c=a-cur;
			ret-=d*((c+1)%mo)%mo*(c%mo)%mo*((2*c+1)%mo)%mo*((mo+1)/6)%mo;
			ret-=d%mo*(cur%mo)%mo*(c%mo)%mo*((c+1)%mo)%mo*((mo+1)/2)%mo;
			
			X-=d*(a+1-cur);
			cur=a+1;
			
		}
		ret=(ret%mo+mo)%mo;
		cout<<ret<<endl;
		
	}
}

まとめ

B[i]=A[i]/iに考えが至らないのはまずかったな。