GoldenPotato137的小屋

反演
反演

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

题面 传送门:洛咕 Solution 调到自闭,我好菜啊 为了方便讨论,以下式子$m>=n$ 为了方便书写,以下式子中的除号均为向下取整 我们来颓柿子吧qwq 显然,题目让我们求: $\large \sum_{i=1}^n\sum_{j=1}^m lcm(i,j)$ $lcm$没法玩,我们转到$gcd$形式: $\large \sum_{i=1}^n\sum_{j=1}^m \frac{i*j}{gcd(i,j)}$ 根据套路,我们去枚举$gcd$ $\large \sum_{i=1}^n\sum_{j=1…

2019年3月5日 0条评论 461点热度 0人点赞 GoldenPotato137 阅读全文
反演

[Luogu P2522] [HAOI2011]Problem b

题面 传送门:洛咕 Solution 我怎么只会刷水题 这题的双倍经验题,不多说啥了。 啥?范围不一样? 那根据我们写数位DP及二维前缀和的经验,我们容斥一下...... 然后就没有然后了。 时间复杂度$O(m*\sqrt n)$ Code 人傻自带大常数,不开O2 T一个点 事实上这题可以把一些不必要的$longlong$改成$int$,刚好能过。可惜我太颓,不想改了 //Luogu P2522 [HAOI2011]Problem b //Jan,23rd,2019 //莫比乌斯函数双倍经验题 #include&…

2019年3月5日 0条评论 618点热度 0人点赞 GoldenPotato137 阅读全文
反演

[Luogu P3327] [SDOI2015]约数个数和

题面: 传送门:洛咕 Solution 首先,我们需要一个结论: $\large d(i,j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ 证明 理性证明请看这篇博客的例五 本蒟蒻提供一个感性证明的方法:如果$x*y$是$i*j$的因数,我们必须有$x|i,y|j$,而后面那个$gcd(x,y)$是用来去重的 有了这个柿子之后,我们之后的推导就比较套路了: 为了方便讨论,之后的柿子均默认$m>n$ 为了方便书写,之后的除法默认向下取整 原式: $\large \sum_{i=…

2019年3月5日 0条评论 590点热度 0人点赞 GoldenPotato137 阅读全文
反演

[Luogu P3455] [POI2007]ZAP-Queries

题面 传送门:洛咕 Solution 这题比这题不懂简单到哪里去了 好吧,我们来颓柿子。 为了防止重名,以下所有柿子中的$x$既是题目中的$d$ 为了方便讨论,以下柿子均假设$b>=a$ 为了方便书写,以下除号均为向下取整 题目要求的显然是: $\large \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=x]$ 根据套路,我们这里要先把这个$x$除掉 $\large \sum_{i=1}^{a/x}\sum_{j=1}^{b/x}[gcd(i,j)=1]$ 再根据套路,根据莫比乌斯函数…

2019年3月4日 0条评论 446点热度 0人点赞 GoldenPotato137 阅读全文
反演

[Luogu P2257] YY的GCD

题面 传送门:洛咕 Solution 推到自闭,我好菜啊 显然,这题让我们求: $\large \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]$ 根据套路,我们可以把判断是否为质数改为枚举这个质数,有: 为了方便枚举,我们在这里假设有$m>n$ $\large \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{k\in prime}^{n}[gcd(i,j)= k]$ 显然,要让$gcd(i,j)=k$,必须要有$i,j$均为$k$的倍数,因此有: …

2019年3月4日 0条评论 621点热度 0人点赞 GoldenPotato137 阅读全文

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

最近评论
hilaolu 发布于 1 年前(03月16日) 球球屑gp翻我展示一下ua屑屑
Guava 发布于 1 年前(11月30日) @GoldenPotato137 暂时是 guavaoj.tk
碱式碳酸希 发布于 1 年前(11月30日) 可以先不要告诉老师们吗(偷偷搞的
碱式碳酸希 发布于 2 年前(11月04日) %%%%Tql 请求搬运至NNEZ校内OJ公告中。 展示链接: 请在启天楼内网中访问! :razz:...
630分苦苦挣扎的菜鸡土豆 发布于 2 年前(05月01日) 肥肠抱歉,刚刚看见呢。 那个发送留言不能立刻看见源于我站挂了个腾讯云cdn,默认会返缓存的内容qwq...
分类
  • CDQ分治
  • DAG DP
  • DP+DP
  • FFT/NTT
  • Kruskal重构树
  • LCT
  • LUCAS
  • NNEZ
  • set
  • splay
  • 主席树
  • 二分/二分答案
  • 位运算
  • 倍增
  • 其他
  • 分块
  • 动态规划
  • 卷积
  • 反演
  • 同余
  • 后缀数组
  • 后缀自动机
  • 哈希
  • 图论
  • 圆方树
  • 堆
  • 多项式
  • 字符串
  • 学习笔记
  • 容斥
  • 容斥
  • 左偏树
  • 并查集
  • 数位DP
  • 数学
  • 数据结构
  • 整体二分
  • 斯特林数
  • 最小割
  • 最短路径
  • 未分类
  • 树套树
  • 树形DP
  • 模拟
  • 深度学习
  • 游记/自闭记/滚粗记
  • 点分治
  • 状压DP
  • 生涯纪录
  • 线段树
  • 组合数学
  • 缩点/强连通分量
  • 网格DP
  • 网络最大流
  • 网络流
  • 背包DP
  • 虚树
  • 贪心
  • 边双/点双
归档
  • 2022年1月
  • 2021年9月
  • 2021年3月
  • 2021年2月
  • 2019年11月
  • 2019年4月
  • 2019年3月
  • 2019年2月

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号