BZOJ_2693_jzptab_莫比乌斯反演
BZOJ_2693_jzptab_莫比乌斯反演
Description
Input
一个正整数T表示数据组数
接下来T行 每行两个正整数 表示N、M
Output
T行 每行一个整数 表示第i组数据的结果
Sample Input
4 5
Sample Output
122
HINT
T <= 10000
N, M<=10000000
$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$
$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i*j}{gcd(i,j)}$
$=\sum\limits_{p=1}^{n}\sum\limits_{i=1}^{\lfloor\frac{n}{p} \rfloor}
\sum\limits_{j=1}^{\lfloor\frac{m}{p} \rfloor} i*j*p*[gcd(i,j)=1]$
$=\sum\limits_{p=1}^{n}p\sum\limits_{i=1}^{\lfloor\frac{n}{p} \rfloor}
\sum\limits_{j=1}^{\lfloor\frac{m}{p} \rfloor} i*j
\sum\limits_{d|gcd(i,j)}\mu(d)$
$=\sum\limits_{p=1}^{n}p
\sum\limits_{d=1}^{n/p}\mu(d)*d^{2}
\sum\limits_{i=1}^{\lfloor\frac{n/p}{d} \rfloor}
\sum\limits_{j=1}^{\lfloor\frac{m/p}{d} \rfloor} i*j
$
设$s[n]=\sum\limits_{i=1}^{n}i$
$=\sum\limits_{p=1}^{n}p
\sum\limits_{d=1}^{n/p}\mu(d)*d^{2}*
s[\lfloor\frac{n/p}{d} \rfloor]*
s[\lfloor\frac{m/p}{d} \rfloor]
$
设$Q=d*p,先枚举Q$
$=\sum\limits_{Q=1}^{n}
s[\lfloor\frac{n}{Q} \rfloor]*
s[\lfloor\frac{m}{Q} \rfloor]
\sum\limits_{d|Q}\mu(d)*d^{2}*\lfloor\frac{Q}{d} \rfloor
$
设$f[n]=\sum\limits_{d|n}\mu(d)*d^{2}*\lfloor\frac{n}{d} \rfloor
=n\sum\limits_{d|n}\mu(d)*d$
$=\sum\limits_{Q=1}^{n}
s[\lfloor\frac{n}{Q} \rfloor]*
s[\lfloor\frac{m}{Q} \rfloor]*f[Q]
$
$然后发现f[n]=n*g[n],g[n]为 id卷\mu 的积性函数$
$我们可以处理出f[n]的前缀和,然后O(\sqrt{n})处理即可$
$mdlswl$
最新文章
- 【先定一个小目标】在Windows下的安装Elasticsearch
- C#在winform中调用系统控制台输出
- SVN钩子说明
- 2014-2015 ACM-ICPC, NEERC, Moscow Subregional Contest E. Equal Digits
- 在Java中导出word、excel格式文件时JSP页面头的设置
- 通过ros节点发布Twist Messages控制机器人--10
- 商品标签例子——CSS3 transform 属性
- iOS App 自定义 URL Scheme 设计(转自COCOACHINA)
- 【HDU 4452 Running Rabbits】简单模拟
- HTML介绍JS
- redis分布式锁的几种实现方式,以及Redisson的配置和使用
- Gradle 的Daemon配置
- 调用链监控 CAT 之 入门
- Java+selenium+feeder+AutoIt+自动加载插件
- ant+svn+tomcat实现自动构建
- WCF开发框架形成之旅---WCF的几种寄宿方式
- iconfont.cn批量加入
- 数据驱动测试二:使用TestNG和CSV文件进行数据驱动
- Elasticsearch 过滤器
- spring boot学习(2) SpringBoot 项目属性配置