JZOJ 4496 「GDOI2016」互补约数

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

首先有 n∑i=1∑d|igcd(d,id)=n∑d=1∑id≤ngcd(d,i)=∑k≤nk∑dk≤n∑idk≤n[gcd(d,i)=1]

然鹅推到这里你会发现自己推错了，由于两个都除以了 k，所以上界需要修正。 ∑k2≤nk∑dk2≤n∑idk2≤n[gcd(d,i)=1]=∑k2≤nk∑dk2≤n∑j|gcd(d,i)μ(j)=∑k2≤nk∑j2k2≤nμ(j)∑dj2k2≤n⌊ndj2k2⌋=⌊√n⌋∑k=1k⌊√⌊nk2⌋⌋∑j=1μ(j)⌊nj2k2⌋∑d=1⌊ndj2k2⌋

后面那个东西其实就是约数个数前缀和，不过用这个方法的话还要带个杜教筛。

复杂度证明： ⌊√n⌋∑i=1√ni2=⌊√n⌋∑i=1√ni=O(√nlogn)

故这个方法的复杂度是 O(√nlogn+n2/3) 的。

另一种方法：利用欧拉函数的性质 φ∗1=ID。
证明：
原式即 ∑d|nφ(d)=n。
考虑将 [1,n] 中的所有数按照和 n 的 gcd 分类，即 Cd={x|x∈[1,n],gcd(x,n)=d}。
那么显然每个数都有唯一对应的 Cd，于是有 ∑d|n|Cd|=n（注意 d|n 时才有贡献）。
然后又发现，|Cd|=n∑i=1[gcd(i,n)=d]=nd∑i=1[gcd(i,nd)=1]=φ(nd)。
证毕。

重新来过： n∑i=1∑d|igcd(d,id)=n∑d=1∑id≤ngcd(d,i)=n∑d=1∑id≤n∑k|gcd(d,i)φ(k)=∑k2≤nφ(k)∑dk2≤n⌊ndk2⌋=⌊√n⌋∑k=1φ(k)⌊nk2⌋∑d=1⌊ndk2⌋

线性筛之后暴力计算……
该做法的复杂度是 O(√nlogn)，证明类似。
代码是第二种做法的（懒得敲杜教筛

代码：

#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);
}