﻿ P4844 LJJ爱数数

P4844 LJJ爱数数

## 做法

(sumlimits_{a=1}^nsumlimits_{b=1}^nsumlimits_{c=1}^n[gcd(a,b,c)=1&&frac{1}{a}+frac{1}{b}=frac{1}{c}])

([gcd(a,b,c)=1])这个好理解，但后面(frac{1}{a}+frac{1}{b}=frac{1}{c})怎么办呢？

(g=gcd(a,b),A=frac{a}{g},B=frac{b}{g})

( herefore frac{(A+B)c}{g}=AB)(g)要整除((A+B)c)

( herefore frac{A+B}{g}=frac{AB}{c})，设(p=frac{A+B}{g}=frac{AB}{c})

(c=frac{A+B}{g} Longrightarrow p)整除同时整除(A,B)

(g=gcd(a,b),A=frac{a}{g},B=frac{b}{g} Longrightarrow A,B)互质

( herefore p=1)

( herefore A+B=g Longrightarrow a+b=g^2,c=AB Longrightarrow c=frac{ab}{g^2})

[egin{aligned} Ans & =sumlimits_{g=1}^{sqrt {2n}}sumlimits_{i=1}^{frac{n}{g}}[gcd(ig,g^2-ig)=g]\ &=sumlimits_{g=1}^{sqrt {2n}}sumlimits_{i=1}^{frac{n}{g}}[gcd(i,g-i)=1]\ &=sumlimits_{g=1}^{sqrt {2n}}sumlimits_{i=1}^{frac{n}{g}}[gcd(i,g)=1]\ end{aligned}]

[egin{aligned} sumlimits_{i=1}^k[gcd(i,g)=1]&=sumlimits_{i=1}^ksumlimits_{j|gcd(i,g)}mu(j)\ &=sumlimits_{i=1}^ksumlimits_{j=1}^gmu(j)[j|g][j|]\ &=sumlimits_{j|g}mu(j)frac{k}{j}\ end{aligned}]

## My complete code

``````#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=15000000;
LL x(0),f(1); char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
int mu[maxn],prime[maxn];
bool visit[maxn];
inline void F_phi(int N){
mu[1]=1; int tot(0);
for(int i=2;i<=N;++i){
if(!visit[i])
prime[++tot]=i,
mu[i]=-1;
for(int j=1;j<=tot&&i*prime[j]<=N;++j){
visit[i*prime[j]]=true;
if(i%prime[j]==0)
break;
else
mu[i*prime[j]]=-mu[i];
}
}
}
LL Up;
int n;
struct node{
int val,next;
}dis[maxn];
int num;
}
inline LL Get(int d,int k){
LL ret(0);
ret+=k/dis[i].val;
return ret;
}
int main(){
n=sqrt(2*Up);
F_phi(n);
for(int i=1;i<=n;++i)
for(int j=1;1ll*j*i<=1ll*n;++j)
if(mu[j])