# [51nod] [product function] [Dujiao sieve] sum of the greatest common divisor V3

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1237

## sol:

I didn't want to do the nude question, but the previous question always needs to be adjusted, so it's not beautiful
This question has passed at last. I feel that I have almost found the debugging pit.

The essence of Du jiaoshai seems to have grasped a little.
Simple inversion

∑ndd∑ndi∑ndj(i,j)=1∑dnd∑ind∑jnd(i,j)=1
∑ndd(2(∑ndjϕ(i))−1)∑dnd(2(∑jndϕ(i))−1)
Screen phi. The phi here is not in the way of tangls, but in the way of routine derivation. I feel that it is very common.

```#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long ll;

ll n;

{
char c;
bool pd=0;
while((c=getchar())>'9'||c<'0')
if(c=='-') pd=1;
int res=c-'0';
while((c=getchar())>='0'&&c<='9')
res=(res<<3)+(res<<1)+c-'0';
return pd?-res:res;
}
const int N=1e6;
const int pyz=1e9+7;
int inv2;
int phi[N+7],s[N+7];
inline int ksm(int s,int t)
{
int res=1;
while(t)
{
if(t&1) res=(ll)res*s%pyz;
s=(ll)s*s%pyz;
t>>=1;
}
return res;
}
inline get_f(ll x)
{
if(x<=N) return phi[x];
if(s[n/x]) return s[n/x];
s[n/x]=(ll)x%pyz*(x%pyz+1)%pyz*inv2%pyz;
ll a,b;
for(ll i=2;i<=x;++i)
{
a=x/i;
b=x/a;
s[n/x]=(s[n/x]-(ll)get_f(a)*((b-i+1)%pyz)%pyz+pyz)%pyz;
i=b;
}
return s[n/x];
}
int prime[N];
bool is[N+7];
int main()
{
//  freopen("1237.in","r",stdin);
//  freopen(".out","w",stdout);
cin>>n;
inv2=ksm(2,pyz-2);
ll a,b,ans=0;
phi=1;
for(int i=2;i<=N;++i)
{
if(!is[i]) prime[++prime]=i,phi[i]=i-1;
for(int j=1;j<=prime&&i*prime[j]<=N;++j)
{
is[i*prime[j]]=1;
if(!(i%prime[j]))
{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
phi[i]=(phi[i-1]+phi[i])%pyz;
}
for(ll i=1;i<=n;++i)
{
a=n/i;
b=n/a;
ans=(ans+(i+b)%pyz*((b-i+1)%pyz)%pyz*inv2%pyz*(2*get_f(a)%pyz-1)%pyz)%pyz;
i=b;
}
ans=(ans+pyz)%pyz;
cout<<ans;
}
```

Posted on Fri, 03 Apr 2020 23:27:42 -0700 by interrupt