JZOJ 4496.「GDOI2016」互补约数

瞎起的名字……不要吐槽不符合反演的定义之类的……

首先有

然鹅推到这里你会发现自己推错了,由于两个都除以了 kk,所以上界需要修正。

后面这个式子中的 j2k2j^2 k^2 据说只有 O(n)O(\sqrt n) 种取值,然鹅我并不会证(逃

另一种方法:利用欧拉函数的性质 φ1=ID\varphi * \mathbb 1 = \text{ID}
证明:
原式即 dnφ(d)=n\sum\limits_{d | n} \varphi(d) = n
考虑将 [1,n][1,n] 中的所有数按照和 nngcd\gcd 分类,即 Cd={xx[1,n],gcd(x,n)=d}C_d = \{x|x \in [1,n],\gcd(x,n) = d\}
那么显然每个数都有唯一对应的 CdC_d,于是有 dnCd=n\sum\limits_{d | n} |C_d| = n(注意 dnd|n 时才有贡献)。
然后又发现,Cd=i=1n[gcd(i,n)=d]=i=1nd[gcd(i,nd)=1]=φ(nd)|C_d| = \sum\limits_{i = 1}^n [\gcd(i,n) = d] = \sum\limits_{i = 1}^{\frac n d} [\gcd(i,\dfrac n d) = 1] = \varphi(\dfrac n d)
证毕。

重新来过:

线性筛之后暴力计算……
然后这个东西复杂度我也不会算,反正是亚线性的。
以下代码为此做法。

代码:

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
#include <cstdio>
#include <cmath>
using namespace std;
const long long N = 1e11;
const int MX = 32e4;
long long n;
int mx,vis[MX + 5],cnt,prime[MX + 5],phi[MX + 5];
long long ans,cur,bound;
int main()
{
freopen("gcd.in","r",stdin),freopen("gcd.out","w",stdout);
scanf("%lld",&n),mx = sqrt(n),phi[1] = 1;
for(register int i = 2;i <= mx;++i)
{
if(!vis[i])
phi[prime[++cnt] = i] = i - 1;
for(register int j = 1;j <= cnt && i * prime[j] <= mx;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
{
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for(register int i = 1;i <= mx;++i)
{
cur = 0,bound = n / i / i;
for(register long long l = 1,r;l <= bound;l = r + 1)
{
r = bound / (bound / l);
cur += (bound / l) * (r - l + 1);
}
ans += cur * phi[i];
}
printf("%lld\n",ans);
}