记录编号	425981	评测结果	WWWWWWWWWWWWWWWWWWWWWWWWW
题目名称	[UVA 11426] [济南集训 2017] 求gcd之和	最终得分	0
用户昵称	_Itachi	是否通过	未通过
代码语言	C++	运行时间	0.374 s
提交时间	2017-07-16 14:10:45	内存使用	23.56 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int HASH=1000003,SIZEN=HASH+10,INF=998244353,inv2=(INF+1)>>1;
struct Rabit_tree{int next,v;LL to;};
struct Rabit_HASH{
	int head[SIZEN],len;Rabit_tree e[SIZEN];
	Rabit_HASH(){len=1;memset(head,0,sizeof(head));}
	void set(LL x,int key){
		int rt=x%HASH,i;
		for(i=head[rt];i;i=e[i].next)
			if(e[i].to==x)return;
		e[++len].to=x,e[len].next=head[rt],head[rt]=len,e[len].v=key;
	}
	int get(LL x){
		int rt=x%HASH,i;
		for(i=head[rt];i;i=e[i].next)
			if(e[i].to==x)return e[i].v;
		return INF;
	}
}HA;
const int maxn=1000015;
int phi[maxn],prime[maxn/10],cnt=0,N;
void Rabit_in(){
	int i,j;N=maxn-10,phi[1]=1;
	for(i=2;i<N;i++){
		if(!phi[i])prime[++cnt]=i,phi[i]=i-1;
		for(j=1;j<=cnt;j++){
			if(i*prime[j]>N)break;
			if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
			else {phi[i*prime[j]]=phi[i]*prime[j];break;}
		}
	}
	for(i=1;i<N;i++)phi[i]=(phi[i-1]+phi[i])%INF;
}
int Rabit_sum(LL n){
	n%=INF;
	return ((n*1ll*(n+1))%INF*1ll*inv2)%INF;
}
int Rabit_ans(LL n){
	if(n<N)return phi[n];
	int res=HA.get(n);
	if(res^INF)return res;else res=Rabit_sum(n);
	for(LL i=2,last;i<=n;i=last+1)
		last=n/(n/i),res-=(((last-i+1)%INF)*1ll*Rabit_ans(n/i))%INF,res=(res+INF)%INF;
	HA.set(n,res);
	return res;
}
int Rabit_get(LL n){
	int res=0;
	for(LL i=1,last;i<=n;i=last+1)
		last=n/(n/i),
		res+=(((((n/i)%INF)*1ll*((n/i)%INF))%INF)*1ll*((Rabit_ans(last)-Rabit_ans(i-1)+INF)%INF))%INF,
		res%=INF;
	return res;
}
int main(){
	freopen("hoip.in","r",stdin);freopen("hoip.out","w",stdout);
	Rabit_in();
	LL n;scanf("%lld",&n);
	printf("%d\n",Rabit_get(n)%INF);
}