模板 - 数论 - 整除分块

佚名 6年前 (2019-04-08) 随笔 1366人围观抢沙发百度已收录

//整除分块,n版
ll aliquot_patition(int n) {
    ll ans=0;
    for(int l=1,r; l<=n; l=r+1) {
        r=n/(n/l);
        ans+=1ll*(n/l)*(sum[r]-sum[l-1]);
    }
    return ans;
}


//整除分块,n,m版
ll aliquot_patition(int n,int m) {
    ll ans=0;
    int N=min(n,m);
    for(int l=1,r; l<=N; l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
    }
    return ans;
}

其中sum是指前缀和,而不是别的什么约数的莫比乌斯函数之和之类的.