记录编号	457947	评测结果	AAAAAAAAAA
题目名称	[SYOI 2017] ZF与数论	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	2.089 s
提交时间	2017-10-09 21:01:26	内存使用	30.81 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define mod 998244353
using namespace std;
const int maxn=1000010;
long long L,R,tot;
long long pri[maxn],mark[maxn],phi[maxn],num[maxn];
void GetPrime(){
	for(long long i=2;i<=maxn;i++){
		if(!mark[i])pri[++tot]=i;
		for(long long j=1;j<=tot&&pri[j]*i<=maxn;j++){
			mark[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}
}
long long Cal(){
	long long ans=0;
	for(long long i=0;i<=R-L;i++)num[i]=phi[i]=L+i;
	for(long long i=1;i<=tot;i++){
		if(pri[i]>R)break;
		long long tmp=(long long)ceil(1.0*L/pri[i])*pri[i];
		for(long long k=tmp;k<=R;k+=pri[i]){
			phi[k-L]/=pri[i],phi[k-L]*=(pri[i]-1);
			while(num[k-L]%pri[i]==0)num[k-L]/=pri[i];
		}
	}
	for(long long i=0;i<=R-L;i++)
		if(num[i]!=1)phi[i]/=num[i],phi[i]*=(num[i]-1);
	for(long long i=0;i<=R-L;i++)ans=(ans+phi[i]);
	return ans;
}
int main(){
	freopen("ZFAndMath.in","r",stdin);
	freopen("ZFAndMath.out","w",stdout);
	scanf("%lld%lld",&L,&R);
	GetPrime();
	long long ans=Cal();
	printf("%lld\n",ans%mod);
	return 0;
}