清北学堂Day3

卷积公式（Dirichlet卷积）

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

就是说

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

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

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

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

有一个非常神奇的筛法

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

有一个很有意思的东西

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=1;i*i<=n;i++)
    {
        h[i*j]+=f[i]*g[i];
        for(int j=i+1;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，这是非常悲催的事情

例题：

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

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

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

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

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

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

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

代码实现

xian_xing_shai();

for (int a=1;a<=n;a++)
    sum_mu[a] = sum_mu[a-1] + mu[a];
    
    
int solve(int n,int m)
{
    int ans=0;
    //for (int d=1;d<=n;d++)
    //    ans += mu[d] * (n/d) * (m/d);
    for (int d=1;d<=n;)
    {
        int next_d = min(
            n/(n/d),
            m/(m/d)
        );
        ans += (sum_mu[next_d] - sum_mu[d-1]) * (n/d) * (m/d);
        d=next_d+1;
    }
    return ans;
}