C++ 解法, 执行用时: 2468ms, 内存消耗: 6300K, 提交时间: 2022-01-21 15:15:55

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const int maxn=3e5+10;
ll c[maxn],inv[maxn];
int c0[maxn];
int main(){
	for(int i=0;i<=3e5;i++)c[i]=1;
	memset(c0,0,sizeof(c0));inv[1]=1;
	for(int i=2;i<=3e5;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	int l,r,n;cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l>>r;l--;
		c0[r+1]++;
		for(int j=1,k;j<=r;j=k+1){
			int x=r/j,y=l/j;
			if(y==0)k=r/x;
			else k=min(r/x,l/y);
			int u=x-y;
			if(u==0)c0[j]++,c0[k+1]--;
			else c[j]=c[j]*u%mod,c[k+1]=c[k+1]*inv[u]%mod;
		}
	}
	ll ans=0;
	for(int i=1;i<=3e5;i++){
		c[i]=c[i]*c[i-1]%mod;
		c0[i]+=c0[i-1];
		if(!c0[i])ans=(ans+c[i])%mod;
	}
	cout<<ans<<endl;
}