Description
神炎皇乌利亚很喜欢数对,他想找到神奇的数对。
对于一个整数对(a,b),若满足 a+b<=n 且 a+b 是 ab 的因子,则成为神奇的数对。请问这样的数对共有多少呢?
Input
一行一个整数 n。
Output
一行一个整数表示答案,保证不超过 64 位整数范围。
Sample Input
21
Sample Output
11
Hint
【数据范围与约定】
对于 20%的数据 n<=1000;
对于 40%的数据 n<=100000;
对于 60%的数据 n<=10000000;
对于 80%的数据 n<=1000000000000;
对于 100%的数据 n<=100000000000000。
思路
没有比这更完美的解答:来源
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e7;
int keep[maxn+5],phi[maxn+5],flag[maxn+5],cnt;
long long ans,n;
int main()
{
for(int i=2;i<=maxn;++i)
{
if(!flag[i]) keep[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt,keep[j]*i<=maxn;++j)
{
flag[i*keep[j]]=1;
if(!(i%keep[j])) {phi[i*keep[j]]=phi[i]*keep[j]; break;}
else phi[i*keep[j]]=phi[i]*(keep[j]-1);
}
}
scanf("%lld",&n);
for(long long i=1;i*i<=n;++i) ans+=phi[i]*(n/(i*i));
printf("%lld
",ans);
return 0;
}