首页 > 其他分享 >萌新的莫反练习笔记

萌新的莫反练习笔记

时间:2024-03-13 19:13:13浏览次数:18  
标签:lfloor nonumber frac rfloor sum 笔记 mu 莫反 萌新

萌新的莫反练习笔记

简单的数论函数

恒等函数 \(I(n)=1\)。

元函数 \(e(n)=[n=1]\)。

单位函数 \(id(n)=n\)。

狄利克雷卷积

我们设 \(f\) 和 \(g\) 的卷积 \(f\ast g=F\)。卷积还是一个函数。

那么,\(F(n)=\sum_{d|n}f(d)g(\frac{n}{d})\)。

这就是卷积。

显然,\(e\ast f=f\)。所以 \(e\) 是卷积的单位元。

常用的性质

  • \(f\ast g=g\ast f\)。
  • \((f\ast g)\ast h=g\ast (f\ast h)\)。
  • 若 \(f\),\(g\) 为积性函数,则 \(f∗g\) 为积性函数。
  • \(\varphi\ast I=id\)。

莫反

考虑现在有两个函数 \(f\) 和 \(F\),\(F=f\ast I\)。

如果 \(f\) 易求,我们可以容易地求出 \(F\)。

但是如果 \(F\) 易求,我们考虑如何求出 \(f\)。

我们在等式两边卷上 \(I\) 的逆元即可。

\(I\) 的逆元就是 \(\mu\),即 \(I\ast\mu=e\)。

所以 \(f=F\ast\mu\)。

然后就可以求出 \(f\) 了。可以使用整除分块等实现。

这就是莫反。

P2158 [SDOI2008] 仪仗队

考虑什么样的人不会被挡住。

我们给每个人分配一个坐标,从 \((0,0)\) 到 \((n-1,n-1)\)。

那么,所有 \(gcd(x,y)=1\) 的点就能被看到。

那么,我们要求 \(\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]\)。

开始我们炫酷的计算:

\[\begin{align} &\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=1]\nonumber\\ =&\sum_{i=1}^n\sum_{j=1}^ne(gcd(i,j))\nonumber\\ \end{align} \]

考虑 \(e=I\ast\mu\):

\[\begin{align} &\sum_{i=1}^n\sum_{j=1}^ne(gcd(i,j))\nonumber\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|gcd(i,j)}\mu(d)\nonumber\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,d|j}\mu(d)\nonumber\\ \end{align} \]

考虑先枚举 \(d\):

\[\begin{align} &\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,d|j}\mu(d)\nonumber\\ =&\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)\nonumber\\ =&\sum_{d=1}^n\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{n}{d}\right\rfloor\mu(d)\nonumber\\ \end{align} \]

整除分块解决即可。

P3455 [POI2007] ZAP-Queries

考虑只枚举 \(d\) 的倍数,然后套用上面的式子即可。

P2257 YY的GCD

考虑枚举每个质数,算上面的那个东西。

稍微动动脑子发现复杂度不超过 \(O(n\log n)\)。

查看题解可得复杂度 \(O(\frac{n}{\log n})\)。

P2522 [HAOI2011] Problem b

考虑上面求出的是一个二维前缀和的答案,现在要求矩形,那不是简简单单。

直接套用上面的即可。

P3327 [SDOI2015] 约数个数和

有结论 \(d(nm)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]\)。

考虑感性证明,如果 \(gcd(i,j)>1\) 会算重,不能算。

我们考虑推这个式子。

\[\begin{align} &\sum_{i=1}^n\sum_{j=1}^md(ij)\nonumber\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{x=1}^i\sum_{y=1}^j[gcd(i,j)=1]\nonumber\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{x=1}^i\sum_{y=1}^j\sum_{d|x,d|y}\mu(d)\nonumber\\ =&\sum_{d=1}^n\mu(d)\sum_{i=1}^n\sum_{j=1}^m\sum_{x=1}^{\lfloor\frac{i}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{j}{d}\rfloor}1\nonumber\\ =&\sum_{d=1}^n\mu(d)\sum_{i=1}^n\left\lfloor\frac{i}{d}\right\rfloor\sum_{j=1}^m\left\lfloor\frac{j}{d}\right\rfloor\nonumber\\ \end{align} \]

设 \(s(n)=\sum_{i=1}^n\left\lfloor\frac{i}{d}\right\rfloor\),显然,我们可以整除分块预预处理出 \(s\)。

然后就做完了,复杂度 \(O(n\sqrt{n}+T\sqrt{n})\)。

P1829 [国家集训队] Crash的数字表格 / JZPTAB

直接推式子。

\[\begin{align} &\sum_{i=1}^n\sum_{j=1}^mlcm(i,j)\nonumber\\ =&\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}\nonumber\\ =&\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{d}[gcd(i,j)=d]\nonumber\\ =&\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ijd[gcd(i,j)=1]\nonumber\\ =&\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\sum_{k|i,k|j}\mu(k)\nonumber\\ =&\sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}k^2\mu(k)\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}ij\nonumber\\ =&\sum_{k=1}^nk^2\mu(k)\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}d\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j\nonumber\\ \end{align} \]

后面那两项都是等差数列求和,可以 \(O(1)\) 算。

考虑到我们只对 \(k\) 做整除分块肯定是不行的,所有我们在对 \(k\) 做整除分块的同时对 \(d\) 做整除分块,也就是整除分块套整除分块。

\(x^2\mu(x)\) 可以直接筛出。

最终复杂度为 \(O(\sqrt{n}\times\sqrt{n}+n)=O(n)\)。

AT_agc038_c [AGC038C] LCMs

比上一题多了个限制,\(j>i\)。

我们直接改上面的式子:

\[\sum_{k=1}^nk^2\mu(k)\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}d\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=i+1}^{\lfloor\frac{m}{kd}\rfloor}j\nonumber\\ \]

容易发现后面就是个上三角矩阵求和,用整体减去对角线即可。

时空复杂度不变。

P6156 简单题P6222 「P6156 简单题」加强版

你需要的不是我,而是一篇好的题解。

CYJian 的题解

GoPoux4 的题解

加强版卡空间,但是取模是自然溢出,直接#define int unsigned int即可。

开摆

写不动了,就到这吧

(◉ω◉υ)⁼³₌₃

标签:lfloor,nonumber,frac,rfloor,sum,笔记,mu,莫反,萌新
From: https://www.cnblogs.com/Augury/p/17789620.html

相关文章

  • CSRF&SSRF练习(自用笔记)
    什么是CSRFCSRF(Cross-siterequestforgery)跨站请求伪造:攻击者诱导受害者进入第三方网站,在第三方网站中,向被攻击网站发送跨站请求。利用受害者在被攻击网站已经获取的注册凭证,绕过后台的用户验证,达到冒充用户对被攻击的网站执行某项操作的目的。一个典型的CSRF攻击有着如下的流......
  • 89C52RC定时器(自用复习笔记)
    一、定时器作用(1)用于计时系统,可实现软件计时,或者使用程序每隔一固定时间完成一项操作。(2)替代长时间的Delay,提高CPU的运行效率和处理速度。(3)...操作系统任务切换,多任务执行。二、定时器资源定时器个数:3个(T0、T1、T2),T0,T1与传统51单片机兼容。三、定时器工作原理定时器......
  • 2024年HP笔记本安装Win7虚拟机的过程
    2024年HP笔记本安装Win7虚拟机的过程背景一个项目安装说明指定要求是Win7x64外加firefox+flash的组合。因为Win7已经EOL两年多了flash也EOL快四年了。所以没办法想通过WorkStation进行一下部署和创建。结构发现坑不少。所以记录一下。关于WorkStation的版本部分Wor......
  • 【强化学习笔记一】初识强化学习(定义、应用、分类、性能指标、小车上山案例及代码)
    文章目录第1章初识强化学习1.1强化学习及其关键元素1.2强化学习的应用1.3强化学习的分类1.3.1按任务分类1.3.2按算法分类1.4强化学习算法的性能指标1.5案例:基于Gym库的智能体/环境接口1.5.1安装Gym库1.5.2使用Gym库1.5.3小车上山1.5.3.1有限动作空间1.5.3.2......
  • Vue学习笔记51--解绑组件自定义事件
    解绑组件自定义事件//this.$off('defineMyEvent')//解绑一个自定义事件//解绑多个自定义事件//this.$off(['defineMyEvent','demoEvent'])//等价于this.$off()//解绑所有自定义的事件this.$off()注意:如果vm被销毁,则其所有......
  • 【Python使用】嘿马头条完整开发md笔记第1篇:课程简介,ToutiaoWeb虚拟机使用说明【附代
    嘿马头条项目从到完整开发笔记总结完整教程(附代码资料)主要内容讲述:课程简介,ToutiaoWeb虚拟机使用说明,Pycharm远程开发,产品与开发,数据库1产品介绍,2原型图与UI图,3技术架构,4开发。OSS对象存储,七牛云存储,CDN,缓存。缓存,缓存架构,缓存数据,缓存有效期与淘汰策略,缓存模式缓存数据的......
  • ApeGNN: Node-Wise Adaptive Aggregation in GNNs for Recommendation论文阅读笔记
    Abstract​ 说明现有的问题:现有的gnn平等地对待用户和项目,不能区分每个节点的不同局部模式,这使得它们在推荐场景中并不理想。​ 提出本文的工作:为了解决这一挑战,我们提出了一个节点级自适应图神经网络框架ApeGNN。ApeGNN开发了一种用于信息聚合的节点级自适应融合机制,使每个节点......
  • Stable Diffusion 学习笔记
     对于diffusion的原始论文的理解参考,https://www.bilibili.com/video/BV18a4y1T75X/?p=2&spm_id_from=pageDriver&vd_source=1eb6e5015a1f70daa97080d8ee786d5dhttps://www.bilibili.com/video/BV1KC411Y7AF?p=2&vd_source=1eb6e5015a1f70daa97080d8ee786d5d 之前生成网络,G......
  • Vue学习笔记50--组件自定义事件
    props--将子组件的信息传递给父组件 <!--通过父组件给子组件传递函数类型的props实现:子给父传递数据-->  <School:getShcoolName="getShcoolName"></School>示例一:App.vue<template><divclass="app"><!--<imgsrc="./assets......
  • Springcloud学习笔记62---log.error()打印内容区别
    1. log.error(“异常信息:”+e.getMessage)没有异常信息,没有堆栈信息@PostMapping("/logtest")publicvoidlogtest(){try{inti=1/0;}catch(Exceptione){log.error("异常信息:"+e.getMessage());}......