C++14(g++5.4) 解法, 执行用时: 616ms, 内存消耗: 157432K, 提交时间: 2019-08-06 11:43:55

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int const mod = 998244353;
int const N = 1e7 + 10;
ll l,r;
ll inv[N],sum[N];
void init(){
	inv[1] = 1,	sum[1] = 1;
	for(int i=2;i<N;i++){
		inv[i] = inv[mod % i] * (mod - mod / i) % mod;
		sum[i] = (sum[i-2] + inv[i]) % mod;
	}
}
int main(){
	init();
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%lld%lld",&l,&r);
		int k = (r / l + 1) / 2;
		ll ans = sum[2 * k - 1] - l * inv[r] % mod * k % mod;
		ans %= mod;
		ans = ans * r % mod * inv[r - l] % mod;
		ans = (ans % mod + mod) % mod;
		printf("%lld\n",ans);
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 200ms, 内存消耗: 79116K, 提交时间: 2022-08-11 10:16:39

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P 998244353
int a[20000005],b[20000005],i,l,r,n,t;
int main()
{
	for(a[1]=1,i=2;i<10000005;i++)a[i]=(ll)(P-P/i)*a[P%i]%P;
	for(i=1;i<10000005;i++)
	{
		b[i]=b[i-1]+a[i];
		if(b[i]>=P)b[i]-=P;
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&l,&r);
		n=(r+l)/l>>1;
		printf("%d\n",(r*(b[n<<1]+(ll)(P-1>>1)*b[n]%P)%P-(ll)l*n%P+P)*a[r-l]%P);
	}
	return 0;
}