记录编号	489684	评测结果	AAAAAAAAAA
题目名称	数论函数簇	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	3.214 s
提交时间	2018-03-04 16:26:22	内存使用	4.07 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(int n)
{
	LL i,last,ret=0;
	for(i=1;i<=n;i=last+1)
		last=n/(n/i),ret=(ret+ (   (i+last)*(last-i+1)/2  )%mod*(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];
		}
	}
}
signed main()
{
	// freopen("Ark.in","r",stdin);
	// printf("%d\n",calc(2) );
	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*i<=n;++i)
		ans=(ans+  i*mu[i]%mod*calc( n/(i*i) )%mod  )%mod;
	printf("%lld\n",(ans-( n*(n+1)/2   )%mod+mod)%mod);
	// printf("%lld\n",(ans-gsum(1,n)+mod)%mod);
}
//60000000000
//181604926