记录编号	489659	评测结果	AAAAATTTTT
题目名称	2261.数论函数簇	最终得分	50
用户昵称	LadyLex	是否通过	未通过
代码语言	C++	运行时间	5.027 s
提交时间	2018-03-04 15:50:41	内存使用	5.24 MiB

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define LL long long
#define mod 1005060097
#define inv2 502530049
#define RG register
inline LL gsum(LL l,LL r)
{
	LL ret=(l+r)%mod;
	ret=(r-l+1)%mod*ret%mod;
	return ret*inv2%mod;
}
inline LL calc(LL n)
{
	LL i,last,ret=0;
	for(i=1;i<=n;i=last+1)
		last=n/(n/i),ret=(ret+(n/i)%mod*gsum(i,last)%mod)%mod;
	return ret;
}
#define N 1000010
int mu[N],prime[N/5],tot,lim;
bool vis[N];
LL n;
inline void init()
{
	RG int i,j,tmp;lim=sqrt(n);
	for(mu[1]=1,i=2;i<=lim;++i)
	{
		if(!vis[i])
			prime[++tot]=i,mu[i]=mod-1;
		for(j=1;(tmp=i*prime[j])<=lim;++j)
		{
			vis[tmp]=1;
			if(i%prime[j]==0){mu[tmp]=0;break;}
			mu[tmp]=mod-mu[i];
		}
	}
}
int main()
{
	freopen("functiona.in","r",stdin);
	freopen("functiona.out","w",stdout);
	RG int ans=0;RG LL i;
	scanf("%lld",&n);
	init();
	for(i=1;i<=lim;++i)
		ans=(ans+  i*mu[i]%mod*calc(n/(i*i))%mod  )%mod;
	printf("%lld\n",(ans-gsum(1,n)+mod)%mod);
}