bzoj 2301 [HAOI2011]Problem b（莫比乌斯反演+分块优化）
题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000思路：莫比乌斯反演，ans=solve(b/k,d/k)-s...
[bzoj2301]Problem b莫比乌斯反演+分块优化
题意：$\sum\limits_{\begin{array}{*{20}{c}}{a < = x < = b}\\{c < = y < = d}\end{array}} {\gcd (x,y) = = k} $解题关键：现令$f(i)$表示有多少对${(x,y)}$...
JZYZOJ1518 [haoi2011]b 莫比乌斯反演 分块 容斥
http://172.20.6.3/Problem_Show.asp?id=1518最开始只想到了n^2的写法，肯定要超时的，所以要对求gcd的过程进行优化。首先是前缀和容斥，很好理解。第二个优化大致如下：u为莫比乌斯函数，t为gcd(x,y)为i的倍数的数的个数；满足gcd(x,y)=1的数字对的...
bzoj 2005 能量采集 莫比乌斯反演
我们要求的是∑ni=1∑mj=1(2×gcd(i,j)−1) 化简得2×∑ni=1∑mj=1gcd(i,j)−n×m 所以我们现在只需要求出∑ni=1∑mj=1gcd(i,j)即可 ∑ni=1∑mj=1gcd(i,j) =∑ni=1∑mj=1∑d|gcd(i,j)ϕ(d) =∑min(n,m)d=1...
【数论】【枚举】【莫比乌斯反演】【线性筛】bzoj2818 Gcd
思路是hdu6134的简化版，只需要在外面套上一个枚举素数就行了。http://www.cnblogs.com/autsky-jadek/p/7491730.html#include<cstdio>using namespace std;#define N 10000000bool no...
SPOJ—VLATTICE Visible Lattice Points（莫比乌斯反演）
http://www.spoj.com/problems/VLATTICE/en/题意：给一个长度为N的正方形，从（0,0,0）能看到多少个点。思路：这道题其实和能量采集是差不多的，只不过从二维上升到了三维。分三部分计算：①坐标值上的点，只有3个。②与原点相邻的三个表面上的点，需满足gcd（x，y）...
牛客小白月赛13-J小A的数学题 （莫比乌斯反演）
链接：https://ac.nowcoder.com/acm/contest/549/J来源：牛客网题目描述 小A最近开始研究数论题了，这一次他随手写出来一个式子，∑ni=1∑mj=1gcd(i,j)2∑i=1n∑j=1mgcd(i,j)2，但是他发现他并不太会计算这个式子，你可以告诉他这个结果吗，...
BZOJ 4036: [HAOI2015]按位或 集合幂函数 莫比乌斯变换 莫比乌斯反演
http://www.lydsy.com/JudgeOnline/problem.php?id=4036http://blog.csdn.net/lych_cys/article/details/50898726http://blog.csdn.net/qq_21995319/article/det...
莫比乌斯反演学习笔记（转载自An_Account大佬）
转载自An_Account大佬提示：别用莫比乌斯反演公式，会炸的只需要记住：[gcd(i,j)=1]=∑d∣gcd(i,j)μ(d)[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)[gcd(i,j)=1]=d∣gcd(i,j)∑?μ(d)证明？其实很简单。μ\muμ函数有个性...
POI2007_zap 莫比乌斯反演
题意：http://hzwer.com/4205.html同hdu1695 #include <iostream> #include <cstring> #include <cmath> #include <cstdio> using namespac...
【二分+容斥+莫比乌斯反演】BZOJ2440 完全平方数
Description求第k个没有完全平方因子的数，k<=1e9。Solution这其实就是要求第k个µ[i](莫比乌斯函数)不为0的数。然而k太大数组开不下来是吧，于是这么处理。二分答案x，问题转化为求[1,x]间有多少个没有完全平方因子的数。容斥，加上全部，减去一个质数的平方的倍数个数，加...
luoguP4466 [国际集训队]和与积 莫比乌斯反演
自然想到枚举\(gcd(a, b)\)，不妨设其为\(d\)，并且\(a = di, b = dj(a > b)\)那么\(\frac{ab}{a + b} = \frac{dij}{i + j}\)由于此时有\((i,j) = 1\)，因此\((i, i + j) = (j, i + j) ...
Bzoj 2820: YY的GCD(莫比乌斯反演+除法分块)
2820: YY的GCD Time Limit: 10 Sec Memory Limit: 512 MB Description 神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少...
【BZOJ-2440】完全平方数 容斥原理 + 线性筛莫比乌斯反演函数 + 二分判定
2440: [中山市选2011]完全平方数Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2371 Solved: 1143[Submit][Status][Discuss]Description小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方...
洛谷P3935 Calculating (莫比乌斯反演)
P3935 Calculating题目描述若xx分解质因数结果为\(x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}，令f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)f(x)=(k1+1)(k2+1)⋯(kn+1)，\)求\(\sum_{i=l}^r...
GCD与莫比乌斯反演的勾当
目录机房最后一个学懵逼钨丝的人题目一链接式子注意代码题目链接&&问题公式代码bzoj1101链接式子代码机房最后一个学懵逼钨丝的人题目一链接题目没找到求\(\sum_{1}^{n}\sum_{1}^{m}gcd(i,j)\)式子\(\sum\limits_{i=1}^{N}\sum\...
欧拉函数和莫比乌斯反演（Mobius）
这几天研究了之前一直困扰自己很久的莫比乌斯反演，虽然自己现在学的还不是很好，就简简单单的写一下总结吧，咦，都没学会掌握我就写总结好像很欠揍，欧拉函数现在也系统的整理一下好了 一、欧拉函数 1.定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首...
【BZOJ3994】[SDOI2015]约数个数和 莫比乌斯反演
【BZOJ3994】[SDOI2015]约数个数和Description 设d(x)为x的约数个数，给定N、M，求 Input输入文件包含多组测试数据。第一行，一个整数T，表示测试数据的组数。接下来的T行，每行两个整数N、M。OutputT行，每行一个整数，表示你所求的答案。Sample Inpu...
BZOJ2301 莫比乌斯反演
题意：a<=x<=b，c<=y<=d，求满足gcd(x,y)=k的数对(x,y)的数量 （(x,y)和(y,x)不算同一个）比hdu1695多加了个下界，还有顺序不一样的也算上了。因为G(x,y)本来就是顺序不一样的算不同方案，所以这题的公式就是：Ans=G(...
CF809E Surprise me! 莫比乌斯反演、虚树
传送门简化题意：给出一棵\(n\)个点的树，编号为\(1\)到\(n\)，第\(i\)个点的点权为\(a_i\)，保证序列\(a_i\)是一个\(1\)到\(n\)的排列，求\[\frac{1}{n(n-1)} \sum\limits_{i=1}^n \sum\limits_{j=1}^n \var...