[知识点]莫比乌斯反演入门
因为今天有较为充足的时间，于是果断入坑反演OvO 直接上公式和概念： 定理：$F(n)$和$f(n)$是定义在非负整数集合上的两个函数，并且满足条件，那么我们得到结论 在上面的公式中有一个函数$\mu(d)$，称其为莫比乌斯函数 它的定义如下： （1）若$d=1$，那么$\mu...
BZOJ 1101 [POI2007]Zap（莫比乌斯反演）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1101【题目大意】求[1,n][1,m]内gcd=k的情况【题解】考虑求[1,n][1,m]里gcd=k等价于[1,n/k][1,m/k]里gcd=1考虑求[1,n][1,m]里gcd=1...
51nod 1237 最大公约数之和 V3【欧拉函数||莫比乌斯反演+杜教筛】
用mu写lcm那道卡常卡成狗(然而最后也没卡过去，于是写一下gcd冷静一下首先推一下式子\[\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)\]\[\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{d=1}^{n}[gcd(i,j)==d]d\]\[\sum...
51Nod.1237.最大公约数之和 V3(莫比乌斯反演 杜教筛 欧拉函数)
题目链接\(Description\)\(n\leq 10^{10}\)，求\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\ mod\ (1e9+7)\]\(Solution\)首先\[\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)=\sum_{d=1}^nd...
51nod 1220 约数之和【莫比乌斯反演+杜教筛】
首先由这样一个式子：\( d(ij)=\sum_{p|i}\sum_{q|j}[gcd(p,q)==1]\frac{pj}{q} \)大概感性证明一下吧我不会证然后开始推：\[\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{p|i}\sum_{q|j}[gcd(p,q)==1]\...
【BZOJ4407】于神之怒加强版（莫比乌斯反演）
【BZOJ4407】于神之怒加强版（莫比乌斯反演）题面BZOJ求：\[\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k\]题解根据惯用套路把公约数提出来\[\sum_{d=1}^nd^k\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]\]再提一次\[\s...
51nod1222 最小公倍数计数 莫比乌斯反演 数学
求$\sum_{i = 1}^{n} \sum_{j = 1}^{i} [lcm(i, j) \le n]$因为这样不好求，我们改成求$\sum_{i = 1}^{n} \sum_{j = 1}^{n} [lcm(i, j) \le n]$.这样求出来的值把除了(i, i)这样的点对以外所有点对都重...
[51nod1222] 最小公倍数计数（莫比乌斯反演）
题面传送门题解我此生可能注定要和反演过不去了……死都看不出来为啥它会突然繁衍反演起来啊……设\(f(n)=\sum_{i=1}^n\sum_{j=1}^n[{ij\over\gcd(i,j)}\leq n]\)，这是一个类似前缀的东西，除了\([i,i]\)型的之外每一个二元组都被算了\(2\)次，...
【51nod】1222 最小公倍数计数 莫比乌斯反演+组合计数
【题意】给定a和b，求满足a<=lcm(x,y)<=b && x<y的数对(x,y)个数。a,b<=10^11。【算法】莫比乌斯反演+组合计数【题解】★具体推导过程参考：51nod1222 最小公倍数计数过程运用到的技巧：1.将所有i和j的已知因子提取出来压缩...
51NOD 1222 最小公倍数计数 [莫比乌斯反演 杜教筛]
1222 最小公倍数计数题意：求有多少数对\((a,b):a<b\)满足\(lcm(a,b) \in [1, n]\)\(n \le 10^{11}\)卡内存！枚举\(gcd, \frac{a}{gcd}, \frac{b}{gcd}\)，然后\(\mu\)代入，就是\[\sum_{d=1}^...
【LOJ#572】Misaka Network 与求和（莫比乌斯反演，杜教筛，min_25筛）
【LOJ#572】Misaka Network 与求和（莫比乌斯反演，杜教筛，min_25筛）题面LOJ\[ans=\sum_{i=1}^n\sum_{j=1}^n f(gcd(i,j))^k\]其中\(f(x)\)表示\(x\)的次大质因子。题解这个数据范围不是杜教筛就是\(min\_25\)筛了...
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）题面51NOD\[\sum_{i=1}^n\sum_{j=1}^nsgcd(i,j)^k\]其中\(sgcd\)表示次大公约数。题解明摆着\(sgcd\)就是在\(gcd\)的基础上除掉\(gcd\)的最小因...
LOJ572. 「LibreOJ Round #11」Misaka Network 与求和 [莫比乌斯反演，杜教筛，min_25筛]
传送门思路（以下令\(F(n)=f(n)^k\)）首先肯定要莫比乌斯反演，那么可以推出：\[ans=\sum_{T=1}^n \lfloor\frac n T\rfloor^2\sum_{d|T}F(d)\mu(T/d)\]可以整除分块，但后面的东西怎么办呢？令\(G(T)=F*\mu\)，那么就有...
[复习]莫比乌斯反演,杜教筛,min_25筛
[复习]莫比乌斯反演,杜教筛,min_25筛莫比乌斯反演做题的时候的常用形式：\[\begin{aligned}g(n)&=\sum_{n|d}f(d)\\f(n)&=\sum_{n|d}\mu(\frac{d}{n})g(d)\end{aligned}\]实际上还有\[\begin...
莫比乌斯反演/线性筛/积性函数/杜教筛/min25筛 学习笔记
最近重新系统地学了下这几个知识点，以前没发现他们的联系，这次总结一下。莫比乌斯反演入门：https://blog.csdn.net/litble/article/details/72804050线性筛筛常见积性函数及其代码：https://blog.masterliu.net/algorithm/s...
【BZOJ2820】YY的GCD [莫比乌斯反演]
YY的GCDTime Limit: 10 Sec Memory Limit: 512 MB[Submit][Status][Discuss]Description求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对k。Input第一行一个整数T...
【数论】【枚举】【莫比乌斯反演】【线性筛】bzoj2818 Gcd
思路是hdu6134的简化版，只需要在外面套上一个枚举素数就行了。http://www.cnblogs.com/autsky-jadek/p/7491730.html#include<cstdio>usingnamespacestd;#defineN10000000boolnotpri[...
BZOJ 2818 GCD 【欧拉函数 || 莫比乌斯反演】
传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=28182818:GcdTimeLimit: 10Sec MemoryLimit: 256MBSubmit: 9236 Solved: 4126[Submit][Status][Discus...
【BZOJ】2693: jzptab 莫比乌斯反演
【题意】2154:Crash的数字表格莫比乌斯反演，多组询问，T<=10000。【算法】数论（莫比乌斯反演）【题解】由上一题，$ans=\sum_{g\leqmin(n,m)}g\sum_{d\leqmin(n/g,m/g)}\mu(d)*d^2*sum(n/gd,m/gd)$令T=gd$an...
BZOJ4804 欧拉心算（莫比乌斯反演+欧拉函数+线性筛）
一通套路后得Σφ(d)μ(D/d)⌊n/D⌋2。显然整除分块，问题在于怎么快速计算φ和μ的狄利克雷卷积。积性函数的卷积还是积性函数，那么线性筛即可。因为μ(pc)=0(c>=2)，所以f(pc)还是比较好算的，讨论一波即可。#include<iostream>#include<...