yukicoder : No.1573 Divisor Function

これは典型寄りかな。
https://yukicoder.me/problems/no/1573

問題

f(x,y) := y以下の正整数iのうち、xの約数であるものにおける(x+i)の和
とする。
整数n,mが与えられる。を求めよ。

解法

f(x,y)を言い換えると、(y以下のxの約数)の総和と、(y以下のxの約数の個数)×xの総和となる。
それぞれを数え上げよう。

i*j=xとなるjの個数や総和を数え上げる際、iやjをループするとO(N)やO(M)かかってTLEする。
そこでiとjをそれぞれ√M程度までループすることで数え上げよう。

ll X,Y;
const ll mo=998244353;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	ll ret=0;
	for(y=1;y<=min(Y,100000LL);y++) {
		ll num=X/y;
		ret+=y*num%mo;
		ret+=(num*(num+1)/2)%mo*y%mo;
	}
	for(ll num=1;num<=200000;num++) {
		ll R=X/num;
		ll L=X/(num+1)+1;
		R=min(R,Y);
		L=max(L,100001LL);
		if(L<=R) {
			ll p=(L+R)*(R-L+1)/2%mo;
			ret+=p*num%mo;
			ret+=(num*(num+1)/2)%mo*p%mo;
			
		}
	}
	
	cout<<ret%mo<<endl;
}

まとめ

これも平方分割って言っていいのかな？