2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 2096  Solved: 909 [Submit][Status][Discuss] Description 对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y

Portal Description 进行\(T(T\leq10^5)\)次询问，每次给出\(x_1,x_2,y_1,y_2\)和\(d\)（均不超过\(10^5\)），求\(\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} [gcd(i,j)=d]\)。 Solution 莫比乌斯反演入门题。 设\(calc(n,m)\)表示\(i\in[1,n],j\in[1,m]

https://www.lydsy.com/JudgeOnline/problem.php?id=2301 这道题阔以作为模板莫比乌斯的模板 并且代码里的函数的意义也与标准的相同： f(d,n,m) f ( d , n , m ) f(d,n,m) 代表小于等于 n、m n 、 m n、m 的 gcd(x,y)=d g c d ( x , y ) = d gcd(x,y)=d 的

传送门 很明显类似矩阵前缀和一样查4次 , 然后就是莫比乌斯反演模板了 #include<bits/stdc++.h>#define N 50050#define LL long longusing namespace std;int mu[N],p[N],tot,isp[N],s[N],a,b,c,d,k;LL Q(int n,int m,int k){if(n>m) swap

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=2299 题目大意 给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。 题解 其实就是 (a,b),(a,−b),(b,a),(b,−

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=2298 题目大意 n个人说自己前面有ai个人，后面有bi个人 n个人说自己前面有a_i个人，后面有b_i个人，可能排名相同 询问最少有几个人说谎 题解 通过每个人说的话，我们可以得到这个人所在的区间，即这段人的排名相同 那么如果两个区间有交集且不吻合，那么一定有一个人说谎 吻

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和y的最大公约数。 Input 第一行一个整数n，接下来n行每行五个整数，分别表示a、b、c、d、k

题解： 同BZOJ1101 按照二维前缀和的方式容斥一下即可 //by sdfzchy#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int inf=(1<<30),N=100010;int

Description 近来A国和B国的矛盾激化，为了预防不测，A国准备修建一条长长的防线，当然修建防线的话，肯定要把需要保护的城市修在防线内部了。可是A国上层现在还犹豫不决，到底该把哪些城市作为保护对象呢？又由于A国的经费有限，所以希望你能帮忙完成如下的一个任务： 1.给出你所有的A国城市坐标 2.A国上层经过讨论，考虑到经济问题，决定取消对i城市的保护，也就是说i城市不需要在防线内了