题目本质: 首先有如下结论: 而通过写一写可以发现: 举例来讲,36及其倍数的数,会被1的倍数加一遍,被4的倍数扣一遍,会被9的倍数扣一遍,而为了最终计数为0,需要再加回来一遍,所以在容斥里面是正号. 对于36有:6 = 2 * 3,mu[6] = 1:而同时对比16有:4 = 2 * 2,mu[4] = 0:9有:3 = emmm,mu[3] = -1. 枚举到2时,2*2的倍数被扣一遍:枚举到3时,3*3的倍数被扣一遍:枚举到4时,因为它最终只需要扣一遍,而现在已经满足了,所以跳过:枚举到6

http://172.20.6.3/Problem_Show.asp?id=1518最开始只想到了n^2的写法,肯定要超时的,所以要对求gcd的过程进行优化.首先是前缀和容斥,很好理解.第二个优化大致如下:u为莫比乌斯函数,t为gcd(x,y)为i的倍数的数的个数:满足gcd(x,y)=1的数字对的数量=sigma(1<=i<=min(x,y))u[i]*t[i];t[i]=(x/i)*(y-i);由小数向下取整可知有连续的i满足x/i为定值,y/i也是定值,所以可以分块计算,用u[i]的前缀

题目描述 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 输入输出格式 输入格式: 第一行一个整数n,接下来n行每行五个整数,分别表示a.b.c.d.k 输出格式: 共n行,每行一个整数表示满足要求的数对(x,y)的个数 输入输出样例 输入样例#1: 复制 2 2 5 1 5 1 1 5 1 5 2 输出样例#1: 复制 14 3 说明 100%的数据满足:1≤n≤50000,1≤a≤b≤500

/** 题目:Trees in a Wood. UVA 10214 链接:https://vjudge.net/problem/UVA-10214 题意:给定a,b求 |x|<=a, |y|<=b这个范围内的所有整点不包括原点都种一棵树.求出你站在原点向四周看到的树的数量/总的树的数量的值. 思路: 坐标轴上结果为4,其他四个象限和第一个象限看到的数量一样.所以求出x在[1,a]和y在[1,b]的x/y互质对数即可. 由于a比较小,所以枚举x,然后求每一个x与[1,b]的互质对数. 方法: 1

GuGuFishtion \[ Time Limit: 1500 ms\quad Memory Limit: 65536 kB \] 题意 给出定义\(Gu(a, b) = \frac{\phi(ab)}{\phi(a)\phi(b)}\) 求出\(\sum_{a=1}^{m}\sum_{b=1}^{n}Gu(a,b) (mod p)\) 思路 首先对于欧拉函数,我们知道欧拉函数的朴素式子为:\(\phi(n) = n*(1-\frac{1}{p1})*(1-\frac{1}{p2}) * ..

二分答案,然后用莫比乌斯函数作为容斥系数,计算当前枚举的mid内有几个满足要求的数 #include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=50005; int t,k,mb[N],q[N],tot; bool v[N]; int read() { int r=0; char p=getchar(); while(p>'9'||p<'0'

Description 求第k个没有完全平方因子的数,k<=1e9. Solution 这其实就是要求第k个µ[i](莫比乌斯函数)不为0的数. 然而k太大数组开不下来是吧,于是这么处理. 二分答案x,问题转化为求[1,x]间有多少个没有完全平方因子的数. 容斥,加上全部,减去一个质数的平方的倍数个数,加上两个质数乘积的平方的倍数个数... 然后发现,每个数的系数就是µ 这也说明了莫比乌斯的原理就是容斥,µ函数就是容斥系数 具体来说,对于每一个i<=sqrt(x),对于ans的贡献就是µ[i]

//待更qwq 反演原理 二项式反演 若 \[g_i=\sum_{j=1}^i {\binom ij} f_j\] , 则有 \[ f_i=\sum_{j=1}^i (-1)^{i-j} {i \choose j} g_j \] 同时, 若 \[g_i=\sum_{j=1}^i (-1)^j {i \choose j} f_j\] , 则有 \[f_i=\sum_{j=1}^i (-1)^j {i \choose j} g_j\] 通过反演原理和组合数的性质不难证明. 0/1? todo Sti

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4141    Accepted Submission(s): 1441 Problem Description Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y)

题意:给出n个数$a[i]$,每个数可以变成不大于它的数,现问所有数的gcd大于1的方案数.其中$(n,a[i]<=1e5)$ 思路:鉴于a[i]不大,可以想到枚举gcd的值.考虑一个$gcd(a_1,a_2,a_3…a_n)=d$,显然每个$a_i$的倍数都满足,有$\frac{a_i}{d}$种方案 那么一个d对答案的贡献为\[\prod_{i=1}^{min(a)}{\lfloor\frac{a_i}{d}\rfloor}    \] 但是所有的d计入会有重复情况,考虑容斥,对d进行素数分

题意:求1-b和1-d之内各选一个数组成数对.问最大公约数为k的数对有多少个,数对是有序的.(b,d,k<=100000) 解法1: 这个能够简化成1-b/k 和1-d/k 的互质有序数对的个数. 如果b=b/k.d=d/k,b<=d.欧拉函数能够算出1-b与1-b之内的互质对数.然后在b+1到d的数i,求每一个i在1-b之间有多少互质的数. 解法是容斥,getans函数參数的意义:1-tool中含有rem位置之后的i的质因子的数的个数. 在 ];j++) ans); 这个循环中.ans加的等

题意: 求1 - s 中 找出k个数 使它们的gcd  > 1 求这样的k个数的对数 解析: 从每个素数的倍数中取k个数  求方案数 然后素数组合,容斥一下重的 奇加偶减 莫比乌斯函数的直接套模板就好了 容斥函数为 mu[i] * -1 #include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <

http://acm.hdu.edu.cn/showproblem.php?pid=6390 题意:求一个式子 题解:看题解,写代码 第一行就看不出来,后面的sigma公式也不会化简.mobius也不会 就自己写了个容斥搞一下(才能维持现在的生活) //别人的题解https://blog.csdn.net/luyehao1/article/details/81672837 #include <iostream> #include <cstdio> #include <cstr

2440: [中山市选2011]完全平方数 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 5473  Solved: 2679[Submit][Status][Discuss] Description 小 X 自幼就很喜欢数.但奇怪的是,他十分讨厌完全平方数.他觉得这些数看起来很令人难受.由此,他也讨厌所有是完全平方数的正整数倍的数.然而这丝毫不影响他对其他数的热爱. 这天是小X的生日,小 W 想送一个数给他作为生日礼物.当然他不能送一个小X讨厌

F - Tmutarakan Exams 题意 : 从 < = S 的 数 中 选 出 K 个 不 同 的 数 并 且 gcd > 1 .求方案数. 思路 :记 录 一 下 每 个 数 的 倍 数 vector 存 储 ,最后从 2 开始 遍历 一遍每个数 ,从 他的倍数中 挑选 k个 组合数求解. 但是会有重复,因为 比如 K=2,S=15时 , 2倍数 : 2  ,4 , 6,  8, 10,  12, 14 ,   挑出了 这种情况 6 ,12,然后 从3的倍数 : 3, 6 ,9,12

C - Visible Trees HDU - 2841 思路 :被挡住的那些点(x , y)肯定是 x 与 y不互质.能够由其他坐标的倍数表示,所以就转化成了求那些点 x,y互质 也就是在 1 - m    1 - n 中找互质的对数,容斥 求一下即可 #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 123456 bool vis[maxn+10]; ll t,n,m,prime[m

看到\( 10^10 \)的范围首先想到二分,然后把问题转化为判断\( [1,n] \)内有多少个是某个质数的平方和的数. 所以应该是加上是一个质数的平方的个数减去是两个质数的平方的个数加上是三个质数的平方的个数--注意到这正好是莫比乌斯函数反过来,所以 \( re-=mb[i]*n/(i*i) \) 即可 #include<iostream> #include<cstdio> using namespace std; const int N=300005; int p[N],to

Relatively Prime Powers CodeForces - 1036F Consider some positive integer xx. Its prime factorization will be of form x=2k1⋅3k2⋅5k3⋅-x=2k1⋅3k2⋅5k3⋅- Let's call xx elegant if the greatest common divisor of the sequence k1,k2,-k1,k2,- is equal to 11. F

完全平方数 HYSBZ - 2440 小 X 自幼就很喜欢数.但奇怪的是,他十分讨厌完全平方数.他觉得这些 数看起来很令人难受.由此,他也讨厌所有是完全平方数的正整数倍的数.然而 这丝毫不影响他对其他数的热爱. 这天是小X的生日,小 W 想送一个数给他作为生日礼物.当然他不能送一 个小X讨厌的数.他列出了所有小X不讨厌的数,然后选取了第 K个数送给了 小X.小X很开心地收下了. 然而现在小 W 却记不起送给小X的是哪个数了.你能帮他一下吗? Input 包含多组测试数据.文件第一行有一个整数 T

题面 链接:CF548E Description Mike is a bartender at Rico's bar. At Rico's, they put beer glasses in a special shelf. There are n kinds of beer at Rico's numbered from 1 to n. i-th kind of beer has *a**i* milliliters of foam on it. Maxim is Mike's boss. T