记录编号	454869	评测结果	AAAAAAEEEE
题目名称	2818.[SYOI 2017] ZF与数论	最终得分	60
用户昵称	Fisher.	是否通过	未通过
代码语言	C++	运行时间	0.599 s
提交时间	2017-09-30 08:02:22	内存使用	48.00 MiB

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn=1e7+10;
const int mo=998244353;
int l,r;
int phi[maxn];
vector<int>pri;
bool vis[maxn];
inline void oulashai(int r){
	phi[1]=1;//钦定phi[1]=1; 
	for(int i=2;i<=r;i++){
		if(!vis[i])
			pri.push_back(i),phi[i]=i-1,vis[i]=1;
		for(int j=0;j<pri.size();j++){
			int k=i*pri[j];
			if(k>r)break;
			vis[k]=1;
			if(i%pri[j]==0){
				phi[k]=phi[i]*pri[j];
				break;
			}
			else phi[k]=phi[i]*(pri[j]-1);
		}
	}
}
int main(){
	freopen("ZFAndMath.in","r",stdin);
	freopen("ZFAndMath.out","w",stdout);
	scanf("%d%d",&l,&r);
	oulashai(r);
	long long ans=0;
	for(int i=l;i<=r;i++){
		ans=(ans+(long long)phi[i])%mo;
	}
	printf("%lld\n",ans);
	return 0;
}