Codeforces #853 : Div2 E. Serval and Music Game

割とすんなり全完できた回。
https://codeforces.com/contest/1789/problem/E

問題

N要素の整数列Sが与えられる。
f(x)は、S[i]=P[i]*floor(S[N]/x)+Q[i]*ceil(S[N]/x) を満たす非負整数P[i],Q[i]が存在するiの個数とする。
x*f(x)の総和を求めよ。

解法

前処理としてx=1～S[N]までfloor(S[N]/x)、ceil(S[N]/x)を総当たりしておき、このペアが一致するものはまとめて扱おう。

A=floor(S[N]/x)、B=ceil(S[N]/x)とすると、

• A=Bの場合、f(x)はS中におけるAまたはBの倍数である。
• A=B-1の場合、A*A以上の値は任意に構築可能。S中に現れるA*A未満の値を総当たりしよう。

int T,N;
ll S[1010101];
const ll mo=998244353;
int sum[10101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>S[i];
		FOR(i,S[N-1]+1) sum[i]=0;
		FOR(i,N) sum[S[i]]=1;
		FOR(i,S[N-1]+1) sum[i+1]+=sum[i];
		
		vector<pair<pair<int,int>,ll>> V;
		for(i=1;i<=S[N-1];i++) {
			x=S[N-1]/i;
			y=S[N-1]/i+(S[N-1]%i!=0);
			if(V.empty()||V.back().first!=make_pair(x,y)) V.push_back({{x,y},0});
			V.back().second+=i;
		}
		ll ret=0;
		FORR2(a,v,V) {
			v%=mo;
			if(a.first==a.second) {
				for(x=a.first;x<=S[N-1];x+=a.first) ret+=v*(sum[x]-sum[x-1])%mo;
			}
			else {
				for(x=1;x<a.first;x++) {
					ll L=1LL*x*a.first;
					ll R=min(S[N-1],1LL*x*a.second);
					if(L>R) break;
					ret+=v*(sum[R]-sum[L-1])%mo;
				}
				ll b=1LL*a.first*a.first;
				if(b<=S[N-1]) ret+=v*(sum[S[N-1]]-sum[b-1])%mo;
			}
		}
		cout<<ret%mo<<endl;
	}
}

まとめ

なんか不自然な問題設定だな。
解法から問題作ってそう。