清北学堂Day3

卷积公式（Dirichlet卷积）

清北学堂Day3

这个式子看上去就很变态，那么他是什么意思呢：

就是说

函数f（x）和g（x）对于n的卷积等于n的每一个因子d在f(x)上的值乘上d/n在g(x)上的值的和

例:
设g(n)=φ(n),f(n)=n;

求（f*g）(12)=?;

清北学堂Day3

时间复杂度的话，首先要枚举所有的因子o（sqrt(d) ，所以整个的时间复杂度就是o(n*sqrt(n))

有一个非常神奇的筛法

清北学堂Day3

这个筛法其实和埃氏筛是差不多的，换了个写法而已，但是：
我们用这个循环方式的话，就可以改变时间复杂度

有一个很有意思的东西

1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...=logN；

ll f[N],g[N],h[N];

void calc(int n)

{

    for(int i=;i*i<=n;i++)

    {

        h[i*j]+=f[i]*g[i];

        for(int j=i+;i*j<=n;j++)

            h[i*j]+=f[i]*g[j]+f[j]*g[i];

    }

}

这样这个筛法的时间复杂度可以变成n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...)即o (n logN);

数论题目有一个很好的技巧，只要我们把循环的顺序换一下，很多时候时间复杂度就降下来了，而且数论题目很多也都是考的对算法的优化；很多时候公式推出来了，到最后优化写的不行就直接TLE，这是非常悲催的事情

例题：
清北学堂Day3

清北学堂Day3

[]表示如果为真返回1，否则返回0；

清北学堂Day3

这样就能换成了对所有因子的莫比乌斯函数求值

再换一下，把d放在前面，就大大优化了

清北学堂Day3

这里[ ]是向下取整，要注意不要和上面的判断真假混淆

清北学堂Day3

这里运用了一个非常重要的思想，也就是分块，其实就是通过下取整的方式来把枚举的数字快速筛掉

其实看一下取整函数的图像就能很好发现

清北学堂Day3

实际上n/[n/d]就是区间的右端点

清北学堂Day3

代码实现

xian_xing_shai();

for (int a=;a<=n;a++)

    sum_mu[a] = sum_mu[a-] + mu[a];

int solve(int n,int m)

{

    int ans=;

    //for (int d=1;d<=n;d++)

    //    ans += mu[d] * (n/d) * (m/d);

    for (int d=;d<=n;)

    {

        int next_d = min(

            n/(n/d),

            m/(m/d)

        );

        ans += (sum_mu[next_d] - sum_mu[d-]) * (n/d) * (m/d);

        d=next_d+;

    }

    return ans;

}