Description

很久很久以前，有一只神犇叫yzy;

很久很久之后，有一只蒟蒻叫lty;

Input

请你读入一个整数N;1<=N<=1E9,A、B模1E9+7;

Output

请你输出一个整数A=\sum_{i=1}^N{\mu (i^2)};

请你输出一个整数B=\sum_{i=1}^N{\varphi (i^2)};

Sample Input

1

Sample Output

1

1

Solution

完全不知道第一问是用来干嘛的。。。。反正都是1

第二问，显然，\(\varphi(i^2)=i\times\varphi(i)\)

于是就是求，\(\sum_{i=1}^ni\times\varphi(i)\)

套用杜教筛的式子，\(h=f*g\) ，在 \(f*g\) 中，\(\sum_{d|n}d\times\varphi(d)\times g(\frac{n}{d})\)

一种想法是试着把 \(\frac{n}{d}\) 给去掉，那么尝试着将 \(g\) 定为 \(id\)

那么 \(f*g\) 就变成了 \(n\sum_{d|n}\varphi(d)=n^2\)

带回杜教筛最后的那个式子，得到，\(S(n)=\sum_{i=1}i^2-\sum_{i=2}^niS(\lfloor\frac{n}{i}\rfloor)\)

杜教筛求就好了

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=10000000+10,Mod=1e9+7;

int n,vis[MAXN],prime[MAXN],cnt,phi[MAXN];

ll s[MAXN],inv6;

std::map<int,ll> M;

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

inline void init()

{

	memset(vis,1,sizeof(vis));

	vis[0]=vis[1]=0;

	phi[1]=1;

	for(register int i=2;i<MAXN;++i)

	{

		if(vis[i])

		{

			prime[++cnt]=i;

			phi[i]=i-1;

		}

		for(register int j=1;j<=cnt&&i*prime[j]<MAXN;++j)

		{

			vis[i*prime[j]]=0;

			if(i%prime[j])phi[i*prime[j]]=phi[i]*phi[prime[j]];

			else

			{

				phi[i*prime[j]]=phi[i]*prime[j];

				break;

			}

		}

	}

	for(register int i=1;i<MAXN;++i)s[i]=(s[i-1]+1ll*i*phi[i]%Mod)%Mod;

}

inline ll qexp(ll a,ll b)

{

	ll res=1;

	while(b)

	{

		if(b&1)res=res*a%Mod;

		a=a*a%Mod;

		b>>=1;

	}

	return res;

}

inline ll S(int x)

{

	if(x<MAXN)return s[x];

	if(M.find(x)!=M.end())return M[x];

	ll res=0;

	for(register int i=2;;)

	{

		if(i>x)break;

		int j=x/(x/i);

		(res+=(1ll*(i+j)*(j-i+1)/2)%Mod*S(x/i)%Mod)%=Mod;

		i=j+1;

	}

	return (1ll*x*(x+1)%Mod*(2*x+1)%Mod*inv6%Mod-res+Mod)%Mod;

}

int main()

{

	read(n);init();inv6=qexp(6,Mod-2);

	printf("1\n%lld\n",S(n));

	return 0;

}