BZOJ 3529 [Sdoi2014]数表
发布日期:2021-05-04 16:55:09 浏览次数:52 分类:技术文章

本文共 1746 字,大约阅读时间需要 5 分钟。

题目链接

题解

题目要求

∑ i = 1 n ∑ j = 1 m σ 0 ( gcd ⁡ ( i , j ) ) [ σ 0 ( gcd ⁡ ( i , j ) ) ≤ a ] \sum_{i=1}^n\sum_{j=1}^m \sigma_0(\gcd(i,j))[\sigma_0(\gcd(i,j))\leq a] i=1nj=1mσ0(gcd(i,j))[σ0(gcd(i,j))a]
稍微转化一下就是
∑ T = 1 min ⁡ ⌊ n T ⌋ ⌊ m T ⌋ ∑ k ∣ T μ ( T k ) σ 0 ( k ) [ σ 0 ( k ) ≤ a ] \sum_{T=1}^{\min} \lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{k|T}\mu(\frac{T}{k})\sigma_0(k)[\sigma_0(k)\leq a] T=1minTnTmkTμ(kT)σ0(k)[σ0(k)a]
f ( T ) = ∑ k ∣ T μ ( T k ) σ 0 ( k ) [ σ 0 ( k ) ≤ a ] f(T)=\sum_{k|T}\mu(\frac{T}{k})\sigma_0(k)[\sigma_0(k)\leq a] f(T)=kTμ(kT)σ0(k)[σ0(k)a]
考虑对于每一个 σ 0 ( k ) = a \sigma_0(k)=a σ0(k)=a,更新其在对应位置上的 f f f,可以预处理出 σ 0 \sigma_0 σ0,然后以权值为关键字sort一边,离线处理询问,将询问以 a a a为关键字sort一遍,用树状数组维护每个位置的 f f f

这里有一个小技巧,由于对 2 31 2^{31} 231取模,因此可以利用自然溢出,用unsigned来记录答案,最后取模即可。

时间复杂度 O ( T n log ⁡ n + n log ⁡ 2 n ) O(T\sqrt{n}\log n+n\log^2 n) O(Tn logn+nlog2n)

代码

#include 
#include
int read(){
int x=0,f=1; char ch=getchar(); while((ch<'0')||(ch>'9')) {
if(ch=='-') {
f=-f; } ch=getchar(); } while((ch>='0')&&(ch<='9')) {
x=x*10+ch-'0'; ch=getchar(); } return x*f;} const int maxn=100000;const int maxq=20000;const unsigned mod=1<<31; namespace bit{
unsigned val[maxn+10]; int lowbit(int x) {
return x&(-x); } int add(int pos,unsigned v) {
while(pos<=maxn) {
val[pos]+=v; pos+=lowbit(pos); } return 0; } unsigned getsum(int pos) {
unsigned res=0; while(pos) {
res+=val[pos]; pos-=lowbit(pos); } return res; }} struct data{
int id; unsigned val; bool operator <(const data &other) const {
return val

转载地址:https://blog.csdn.net/wang3312362136/article/details/85952556 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 4176 Lucas的数论
下一篇:BZOJ 3309 DZY Loves Math

发表评论

最新留言

不错!
[***.144.177.141]2024年02月28日 07时46分11秒