记录编号	153984	评测结果	AAAAAAAAATTTTTTTTTTT
题目名称	[国家集训队 2012] 和与积	最终得分	45
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	12.423 s
提交时间	2015-03-20 19:09:43	内存使用	113.80 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

typedef long long int64;

const int Maxn=7000010;

using namespace std;

int tot=0,N;
int64 u[Maxn],prime[Maxn];
bool v[Maxn];

int64 gcd(int64 a,int64 b){
	return b? gcd(b,a%b):a;
}

int64 calc(int64 n,int64 m){
	int64 pos,ans=0;
	for(int64 i=1,nl=min(n,m);i<=nl;i=pos+1){
		pos=min(n/(n/i),m/(m/i));
		ans+=(u[pos]-u[i-1])*(n/i)*(m/i);
	}
	return ans;
}

int main(){
	freopen("nt2012_calc.in","r",stdin);
	freopen("nt2012_calc.out","w",stdout);
	scanf("%d",&N);
	/*u[1]=v[1]=1;
	for(int i=2;i<Maxn;i++){
		if(!v[i]) prime[++tot]=i,u[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<=i;j++){
			u[i*prime[j]]=-u[i];
			if(i%prime[j]==0){
				u[i*prime[j]]=0;
				break;
			}
		}
	}
	for(int i=1;i<Maxn;i++)
		u[i]+=u[i-1];*/
	int64 l=1,r=N,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(mid*mid>=N) r=mid-1;
		else l=mid+1;
	}
	int sqr=l;
	int64 ans=0;
	for(int d=1;d<=sqr-1;d++){
		for(int c=1;c<d;c++)
			if(gcd(c,d)==1LL)
				ans+=(int64)N/(d*(int64)(d+c));
	}
	printf("%lld\n",ans);
	return 0;
}