题目链接
题目思路
其实是一个整除分块的简单题,稍微思考就能写出来
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define fi first
#define se second
#define pii pair<int,int>
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=3e5+5,inf=0x3f3f3f3f,mod=998244353;
const double eps=1e-6;
int n,k;
ll a[maxn],b[maxn];
ll inv[maxn];
ll qpow(ll a,ll b){
ll ans=1,base=a;
while(b){
if(b&1) ans=ans*base%mod;
base=base*base%mod;
b>>=1;
}
return ans;
}
signed main(){
for(int i=0;i<=3e5;i++){
a[i]=1;
inv[i]=qpow(i,mod-2);
}
scanf("%d",&n);
for(int i=1,l,r;i<=n;i++){
scanf("%d%d",&l,&r);
l--;
int nxt;
for(int j=1;j<=3e5;j=nxt+1){
if(j>r){
nxt=3e5;
}else if(j>l){
nxt=r/(r/j);
}else{
nxt=min(r/(r/j),l/(l/j));
}
if(r/j==l/j){
b[j]++;
b[nxt+1]--;
}else{
a[j]=a[j]*(r/j-l/j)%mod;
a[nxt+1]=a[nxt+1]*inv[(r/j-l/j)]%mod;
}
}
}
ll pr=0;
for(int i=1;i<=3e5;i++){
a[i]=a[i-1]*a[i]%mod;
b[i]+=b[i-1];
if(b[i]<=0){
pr=(pr+a[i])%mod;
}
}
printf("%lld\n",pr);
return 0;
}