记录编号	130423	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2012] 和与积	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.553 s
提交时间	2014-10-22 10:46:08	内存使用	0.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
/*设d=gcd(a,b),a=dx,b=dy,则(a+b)|ab<=>(x+y)|d
则d=k(x+y),b=ky(x+y)<=N,设y=p,x+y=q,p<q<2p
*/
typedef long long LL;
const int SIZE=50010;
bool flag[SIZE]={0};
int last[SIZE]={0};
int res[SIZE]={0},rtot;
void resolve(int p){
	rtot=0;
	while(p!=1){
		if(!rtot||last[p]!=res[rtot-1]) res[rtot++]=last[p];
		p/=last[p];
	}
}
bool check_rp(int x){//是否互质?
	for(int i=0;i<rtot;i++) if(x%res[i]==0) return false;
	return true;
}
LL calc_1(int T,int l,int r){//固定p,T=(int)N/p,尝试q从l取到r,此时要求已经分解过
	if(r<l) return 0;
	LL ans=0;
	for(int q=l;q<=r;q++) if(check_rp(q)) ans+=T/q;
	return ans;
}
LL cnt(int l,int r,int d){//l~r内有多少个被d整除的
	int a=(l-1)/d+1,b=r/d;
	if(b<a) return 0;
	return b-a+1;
}
LL calc_d(int T,int d,int l,int r){//固定p,尝试q从l取到r且被d整除
	int a=(l-1)/d+1,b=r/d;//q=dk,k从a到b
	l=a*d,r=b*d;
	LL ans=0;
	for(int x=max(T/r,1);x<=T/l;x++){//统计有多少个T/q=x的q
		ans+=x*cnt(max(T/(x+1)+1,l),min(T/x,r),d);
	}
	return ans;
}
LL DFS(int T,int d,int l,int r,int i,int sgn){
	if(i==rtot){
		return sgn*calc_d(T,d,l,r);
	}
	return DFS(T,d,l,r,i+1,sgn)+DFS(T,d*res[i],l,r,i+1,-sgn);
}
LL calc_2(int T,int l,int r){
	if(r<l) return 0;
	return DFS(T,1,l,r,0,1);
}
LL calc(int N,int p){
	//q从p+1取到2p-1
	resolve(p);
	int T=N/p,k;
	if(!rtot) k=p;
	else k=sqrt(((1<<rtot)*T+0.0)/(rtot+0.0));
	if(k>=2*p) k=2*p;
	if(k<=p) k=p;
	LL ans=calc_1(T,p+1,k);
	ans+=calc_2(T,k+1,2*p-1);
	return ans;
}
void getprime(int n){
	for(int i=2;i<=n;i++){
		if(!flag[i]){
			last[i]=i;
			for(int j=i*i;j<=n;j+=i){
				if(!last[j]) last[j]=i;
				flag[j]=true;
			}
		}
	}
}
void work(void){
	int N;
	scanf("%d",&N);
	int mx=sqrt(N+0.0);
	getprime(mx);
	LL ans=0;
	for(int i=2;i<=mx;i++) ans+=calc(N,i);
	printf("%lld\n",ans);
}
int main(){
	freopen("nt2012_calc.in","r",stdin);
	freopen("nt2012_calc.out","w",stdout);
	work();
	return 0;
}