yukicoder : No.2891 Mint

入力の上限を見ると解法が思いつきそう…。
https://yukicoder.me/problems/no/2891

問題

正整数N,Mが与えられる。
を998244353で割った余りを求めよ。

解法

Nの上限が10^12なので、O(√N)ぐらいの手法が思いつく。
実際、kが10^6までの範囲は愚直に計算しよう。

さて、M%k = M-floor(M/k)*k となる。
kが10^6より大きい場合、floor(M/k)は10^6未満なので、floor(M/k)を1～10^6まで総当たりすればよい。

ll N,M;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ret=0;
	for(i=1;i<=min(2000000LL,N);i++) (ret+=M%i)%=mo;;
	(ret+=(N+1-i)%mo*(M%mo))%=mo;
	
	ll pre=i;
	for(i=2000000;i>=1;i--) {
		ll L=M/(i+1)+1;
		ll R=M/i;
		R=min(R,N);
		L=max(L,pre);
		if(L<=R) {
			ret-=i*((L+R)%mo)%mo*((R-L+1)%mo)%mo*(mo+1)/2;
			ret%=mo;
			
			pre=R+1;
		}
	}
	ret=(ret%mo+mo)%mo;
	cout<<ret<<endl;
	
}

まとめ

これ問題名はなにか意味あるのかな。