博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 3529 [Sdoi2014]数表
阅读量:6836 次
发布时间:2019-06-26

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

题目链接

题解

题目要求

∑i=1n∑j=1mσ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=1min⁡⌊nT⌋⌊mT⌋∑k∣Tμ(Tk)σ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μ(Tk)σ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,更新其在对应位置上的fff,可以预处理出σ0\sigma_0σ0,然后以权值为关键字sort一边,离线处理询问,将询问以aaa为关键字sort一遍,用树状数组维护每个位置的fff

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

时间复杂度O(Tnlog⁡n+nlog⁡2n)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://www.cnblogs.com/Canopus-wym/p/10376078.html

你可能感兴趣的文章
10分钟还原HTTPS真像!
查看>>
单例模式的笔记
查看>>
Linux压力测试工具
查看>>
自由职业一时爽,一直自由一直爽
查看>>
浏览器事件window.onload、o…
查看>>
对象回收时Weak指针自动被置为nil的实现原理
查看>>
php URLEncode() / php URLEncode函数 php urldecode...
查看>>
phpunit mock
查看>>
NodeJS、NPM安装配置步骤(windows版本)
查看>>
mac常用的命令
查看>>
knn 分类
查看>>
【总结】Hadoop中的MultipleOutputs实践
查看>>
测试常见问题
查看>>
SHOP++ 中Hibernate 注解 用法
查看>>
jQuery EasyUI使用教程之创建基本的树网格
查看>>
Fluentd日志处理-插件使用和调试问题(四)
查看>>
实验四 交换机SPAN功能配置 (交换与路由技术)
查看>>
centos7源码安装php5.6并安装pthreads扩展
查看>>
网络基础~linux路由与网关、路由命令
查看>>
强大的联想4U机架式服务器ThinkSystem SR950
查看>>