题目大意
对于一个整数对$(a,b)$，若满足$a+b\le n$且$a+b$是$ab$的因子，则成为神奇的数对。请问这样的数对共有多少呢？
题目分析
设$\gcd(a,b)=gcd$。
设$\frac{a}{gcd}=x,\frac{b}{gcd}=y$，
$\because a+b\mid ab$
$\therefore \gcd(x+y)\mid gcd^2xy$
$\because \gcd(x,y)=1$
$\therefore x+y\mid gcd$
题目问题转化为，统计$x+y\le\frac{n}{gcd}$，$x+y\mid gcd$的个数。
令$x+y=k$。
当$k$一定时，$x+y=k,\gcd(x,y)=1$的个数为$\phi(k)$。
题目问题对$k$的限制过多，尝试将枚举$gcd$转化为枚举$k$。
故问题转化为：统计$gcd\le \frac n{k},gcd$是$k$的倍数的个数。
显然这样的$k$会出现$\frac n{k^2}$次。
故$Ans=\frac{n}{k^2}\phi(k)$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=10000005;
LL n,Phi[maxn],Prime[maxn],ans=0;
int cnt=0;
bool vst[maxn];
void Phi_Table(int n) {
Phi[1]=1;
for(int i=2; i<=n; i++) {
if(!vst[i]) {
Prime[++cnt]=i;
Phi[i]=i-1;
}
for(int j=1; j<=cnt&&Prime[j]*i<=n; j++) {
vst[Prime[j]*i]=1;
if(i%Prime[j]==0) {
Phi[i*Prime[j]]=Phi[i]*Prime[j];
break;
}
Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
}
}
}
int main() {
n=Get_Int();
Phi_Table(sqrt(n)+5);
for(int i=2; i<=sqrt(n); i++)ans+=n/i/i*Phi[i];
printf("%lld\n",ans);
return 0;
}
|
