神炎皇：
题意：
对于一个整数对$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
*/