Bzoj 2301: [HAOI2011]Problem b(莫比乌斯反演+除法分块)
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x...
BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演
2301: [HAOI2011]Problem bTime Limit: 50 Sec Memory Limit: 256 MBSubmit: 1007 Solved: 415[Submit][Status]Description对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，...
[BZOJ1101&BZOJ2301][POI2007]Zap [HAOI2011]Problem b|莫比乌斯反演
对于给定的整数a,b和d，有多少正整数对x,y，满足x<=a，y<=b，并且gcd(x,y)=d。我们可以令F[n]=使得n|(x,y)的数对(x,y)个数这个很容易得到，只需要让x,y中都有n这个因子就好了，也就是[a/n]*[b/n]个数对（向下取整）然后设题中所要求的为f[n],很...
P2522 [HAOI2011]Problem b (莫比乌斯反演)
题目P2522 [HAOI2011]Problem b解析：具体推导过程同P3455 [POI2007]ZAP-Queries不同的是，这个题求的是\(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)=k\)像二维前缀和一样容斥一下，输出就完了。根据luogu某大佬的说法开longl...
洛谷P2257 YY的GCD 莫比乌斯反演
原题链接差不多算自己推出来的第一道题QwQ题目大意\(T\)组询问，每次问你\(1\leqslant x\leqslant N\)，\(1\leqslant y\leqslant M\)中有多少\((x,y)\)满足\(gcd(x,y)\in \mathbb{P}\)数据范围\(T=10000\)，...
【数论】【莫比乌斯反演】【线性筛】bzoj2005 [Noi2010]能量采集
http://blog.csdn.net/Clove_unique/article/details/51089272Key：1、连接平面上某个整点（a,b）到原点的线段上有gcd（a,b）个整点。2、欧拉函数的性质之一：若(N%a==0 && (N/a)%a==0) 则有:phi(N...
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...
【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 最小公倍数计数 [莫比乌斯反演 杜教筛]
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}^...
【51nod】1222 最小公倍数计数 莫比乌斯反演+组合计数
【题意】给定a和b，求满足a<=lcm(x,y)<=b && x<y的数对(x,y)个数。a,b<=10^11。【算法】莫比乌斯反演+组合计数【题解】★具体推导过程参考：51nod1222 最小公倍数计数过程运用到的技巧：1.将所有i和j的已知因子提取出来压缩...
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）
【51NOD 1847】奇怪的数学题（莫比乌斯反演，杜教筛，min_25筛，第二类斯特林数）题面51NOD\[\sum_{i=1}^n\sum_{j=1}^nsgcd(i,j)^k\]其中\(sgcd\)表示次大公约数。题解明摆着\(sgcd\)就是在\(gcd\)的基础上除掉\(gcd\)的最小因...
莫比乌斯反演/线性筛/积性函数/杜教筛/min25筛 学习笔记
最近重新系统地学了下这几个知识点，以前没发现他们的联系，这次总结一下。莫比乌斯反演入门：https://blog.csdn.net/litble/article/details/72804050线性筛筛常见积性函数及其代码：https://blog.masterliu.net/algorithm/s...
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...
【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...
BZOJ 2005 [Noi2010]能量采集 (数学+容斥 或 莫比乌斯反演)
2005: [Noi2010]能量采集Time Limit: 10 Sec Memory Limit: 552 MBSubmit: 4493 Solved: 2695[Submit][Status][Discuss]Description栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可...