怎么又有我不知道的东西啊..自闭了 Description 去年的 Lucas 非常喜欢数论题,但是一年以后的 Lucas 却不那么喜欢了。 在整理以前的试题时,发现了这样一道题目“求 $\sum f(i)$,其中 $1\le i\le ...
莫比乌斯反演
洛谷 P3327 [SDOI2015]约数个数和 题解【莫比乌斯反演】【前缀和】【质因数分解】
有个引理。希望以后这种东西还是能自己推出来 题目描述 设 $d(x)$ 表示 $x$ 的约数个数,给定 $N,M$,求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$。 输入输出格式 输入格式: 输入文件包含多组...
CF1139D Steps to One 题解【莫比乌斯反演】【DP】【枚举】
反演套 DP 的好题(不用反演貌似也能做 但是我不会啊 Description Vivek initially has an empty array $a$ and some integer constant $m$. He performs the following algorithm: Select...
bzoj 2693 jzptab / 洛谷 P1829 Crash的数字表格 题解【莫比乌斯反演】【狄利克雷卷积】
莫比乌斯反演进阶+优化。 Description 求 $$ \sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j) $$ 对 $ 100000009$ 取模输出。 Input 一个正整数 $ T$ 表示数据组数, 接下来 $...
洛谷 P3455 loj #2652 [POI2007]ZAP-Queries 题解【数学】【莫比乌斯反演】
莫比乌斯反演入门题?啊啊啊学了两天。 题目描述 给定正整数 $ a,b,d$,找出满足以下条件的正整数对 $ (x,y)$ 的个数: $ 1 \le x \le a$ $ 1 \le y \le b$ $ \gcd(x,y)=d$ 输入格...