记录编号	396358	评测结果	AAAAAAAAAA
题目名称	等比数列计数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.214 s
提交时间	2017-04-18 19:11:59	内存使用	126.23 MiB

#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e7+10;
int m,cnt,p[N];bool isp[N];
ll n,phi[N];
void init(){
	phi[1]=1;
	for (int i=2;i<=m;i++){
		if (!isp[i]) p[++cnt]=i,phi[i]=i-1;
		for (int j=1;j<=cnt&&i*p[j]<=m;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) phi[x]=phi[i]*(p[j]-1);
				else{phi[x]=phi[i]*p[j];break;}
		}
	}
	for (int i=1;i<=m;i++) phi[i]+=phi[i-1];
}
int main()
{
	freopen("seq_count.in","r",stdin);
	freopen("seq_count.out","w",stdout);
	scanf("%lld",&n);m=sqrt(n);
	init();
	ll ans=0;
	for (ll l,r=n;r;r=l-1){//枚举sqrt(n/i) 
		int k=sqrt(n/r);
		l=n/(k+1)/(k+1)+1;
		ans+=ll(r-l+1)*(phi[k]*2-1);
	}
	printf("%lld\n",ans);
	return 0;
}