记录编号	406212	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] 和与积	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.583 s
提交时间	2017-05-18 09:04:20	内存使用	1.14 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,u[N],p[N],cnt;bool isp[N];
void init(){
	u[1]=1;
	for (int i=2;i<N;i++){
		if (!isp[i]) p[++cnt]=i,u[i]=-1;
		for (int j=1;j<=cnt&&i*p[j]<N;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) u[x]=-u[i];
			else{u[x]=0;break;}
		}
		u[i]+=u[i-1];
	}
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
ll vio(){
	ll ans=0;
	for (int i=1;i<=n;i++)
	for (int j=i+1;j<=n;j++)
		if (!((ll)i*j%(i+j))) ans++;
	return ans;
}
ll calc(int n){
	ll ans=0;
	int m=sqrt(n);
	for (int b=1;b<=m;b++){
		int N=n/b,right=min(N,b*2-1);
		for (int l=b+1,r;l<=right;l=r+1){
			r=min(N/(N/l),right);
			ans+=(r-l+1)*(N/l);
		}
	}
	/*for (int a=1;a<=m*2;a++)
	for (int b=a/2+1;b<a;b++)
		ans+=n/((ll)b*a);
	for (int b=1;b<=m;b++)
	for (int a=b+1;a<b*2;a++)
		ans+=n/((ll)b*a);*/
	return ans;
}
int main()
{
	freopen("nt2012_calc.in","r",stdin);
	freopen("nt2012_calc.out","w",stdout);
	init();
	scanf("%d",&n);
	//printf("%lld\n",vio());
	ll ans=0;
	for (int l,r=sqrt(n);r;r=l-1){
		int k=n/r/r;
		l=sqrt(n/(k+1))+1;
		//printf("k=%d [%d,%d]\n",k,l,r);
		ans+=(u[r]-u[l-1])*calc(k);
	}
	//for (int d=1;(ll)d*d<=n;d++)
	//	if (u[d]) ans+=u[d]*calc(n/d/d);
	printf("%lld\n",ans);
	return 0;
}