神炎皇（模拟测试67）（数论）

神炎皇：

　　题意：

　　　　对于一个整数对$a,b)$，若满足$a+b<=n$且$a+b$是$a*b$的因子，则成为神奇的数对。请问这样的数对共有多少个？（$N<=10^{14}$）

　　题解：

　　　　已知$a+b<=n\ a+b)|ab$。

　　　　设$d=gcda,b),x=a/d,y=b/d$。

　　　　上式为$x+y)*d<=n（1）\ x+y)|x*y*d（2）$。

　　　　因为$gcdx+y,x)=gcdx+y,y)=gcdx,y)=1$。

　　　　（2）式可化减为$x+y)|d$。

　　　　又由（1）式得$x+y)<=sqrt{n}$。

　　　　设$k=x+y,d=z*k$，所以$z*k^2<=n$，那么合法的$d$的个数为$lfloor frac{n}{k^2} floor$。

　　　　而对于每一个$d$，都有$varphik)$个$x$满足条件。

　　　　所以最后答案为$sum limits_{i=1}^{sqrt{n}} varphii) * lfloor frac{n}{k^2} floor$

　　code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define R register
#define ll long long
#define int long long
inline int read)
{
	int aa=0;char cc=getchar);
	whilecc<'0'||cc>'9')cc=getchar);
	whilecc<='9'&&cc>='0')
		aa=aa<<3)+aa<<1)+cc^48),cc=getchar);
	return aa;
}
const int N=1e7+7,M=1e6;
int n,ans;bool mark[N];int tot,phi[N],prime[M];
void getphiconst int lim)
{
	forR int i=2;i<=lim;++i){
		if!mark[i])prime[++tot]=i,phi[i]=i-1;
		forR int j=1;j<=tot;++j){
			ifi*prime[j]>lim)break;
			mark[i*prime[j]]=1;
			ifi%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];break;
			}
			else phi[i*prime[j]]=phi[i]*prime[j]-1);
		}
	}
}
signed main)
{
	//freopen"uria.in","r",stdin);
	//freopen"uria.out","w",stdout);
	n=read);
	const int lim=sqrtn);
	getphilim+2);
	forR int i=1;i<=lim;++i)
		ans+=phi[i]*n/i*i));
	printf"%lld",ans);
	return 0;
}
/*
21 
*/