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=1∑nj=1∑mσ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=1∑min⌊Tn⌋⌊Tm⌋k∣T∑μ(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)=k∣T∑μ(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(Tnlogn+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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年02月28日 07时46分11秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
XSD标准架构-----<xsd:element> 元素详解
2019-04-21
Windows 7下配置JDK环境变量,JAVA环境变量配置,Tomcat服务器的使用
2019-04-21
[POJ1149 Pigs]
2019-04-21
前台table里的值通过npoi导出excle
2019-04-21
VSCode设置中文语言显示
2019-04-21
2 变量、运算符、位运算
2019-04-21
C++虚函数
2019-04-21
Git 标签管理
2019-04-21
MySQL 安装与配置
2019-04-21
Splash Lua 脚本
2019-04-21
Redis在linux环境下的安装
2019-04-21
javascript从定义到执行 js引擎 闭包
2019-04-21
smarty缓存函数
2019-04-21
Mysql配置优化
2019-04-21
SQL的四种连接(左外连接、右外连接、内连接、全连接)
2019-04-21
C语言编程
2019-04-21
Bootstrap基础10(标签页)
2019-04-21
Vue系列之 => 自定义全局指定让文本框自动获取焦点
2019-04-21
前端学习之路-CSS介绍,Html介绍,JavaScript介绍
2019-04-21
PHP全栈从入门到精通1
2019-04-21