yukicoder : No.3377 Sigma Index × A Problems

ややこしいがコードは短い。
https://yukicoder.me/problems/no/3377

問題

f(L,R)を以下のように定義する。
数列Aを、各要素[L,R]の範囲の整数を取るとき、A[i]*iが一定にできるような最長の長さ

整数Nが与えられる。を求めよ。

解法

g(L,R,K) := f(L,R)がK以上なら1、そうでないなら0
とすると、解はとなる。

h(K)=LCM(1,...,K)とする。
g(L,R,K)が1となる条件は、Rを定めるとA[K]=(R以下のうち、h(K)の倍数の最大値)とし、A[1]=A[K]/KがL以上であればよいことになる。
よって三重のsumのうち内側２つの総和は、となる。
h(K)≦NとなるのはKが40以下なので、そこまでKを総当たりすればよい。

int T;
ll N;

vector<ll> LCM={1,1};
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=2;i<=40;i++) {
		LCM.push_back(LCM.back()*(i/__gcd(1LL*i,LCM.back())));
	}
	
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		ll ret=0;
		for(i=1;i<=40;i++) {
			ll l=LCM[i];
			ll a=N/l%mo;
			(ret+=(l/i%mo)*((N+1)%mo*a%mo+mo-a*(a+1)/2%mo*(l%mo)%mo))%=mo;
		}
		cout<<ret<<endl;
	}
}

まとめ

意外に計算時間は短くて済む。