Calculating [整除分块]

本文主要是介绍Calculating [整除分块]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

根据小学奥数知识 , 要求的就是1-n的所有数的约数个数和

我们从每个约数i的贡献考虑 , i的贡献即为 [n/i] 这里向下取整

所以要求的就是

这里用整除分块可以降到

---

 介绍一下整除分块 , 一般用于上面这一类式子

我们发现有一段区间n/i是相等的 , 不妨设为l和r , 满足

[n/l] = [n/r] = x

当 r  等于 [n / x]

根据取整的性质    所以如果r再加1那么  显然不满足相等

根据这一点我们可以写出代码

for(LL l=1,r;l<=n;l=r+1){r = n/(n/l);ans = (ans + (r-l+1) * (n/l)) % Mod;//长度*值
}

---

取模先模再加再模 

#include<bits/stdc++.h>
#define LL long long
#define Mod 998244353
using namespace std;
LL l,r;
LL calc(LL n){LL ans=0;for(LL l=1,r;l<=n;l=r+1){r = n/(n/l);ans = (ans + (r-l+1) * (n/l)) % Mod;}return ans;
}
int main(){scanf("%lld%lld",&l,&r);printf("%lld",((calc(r)-calc(l-1))%Mod+Mod)%Mod);return 0; 
}

 

这篇关于Calculating [整除分块]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---