题目描述对于给出的$n$个询问，每次求有多少个数对$(x,y)$，满足$a \le x \le b$，$c \le y \le d$，且$\gcd(x,y) = k$，$\gcd(x,y)$函数为$x$和$y$的最大公约数。 题解莫比乌斯反演 我们可以用二维前缀和的思想，我们设 $f(n,m)=\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j...

【题目描述】今天的数学课上，Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数$a$和$b$，$\operatorname{lcm}(a,b)$表示能同时被$a$和$b$整除的最小正整数。例如，$\operatorname{lcm}(6,8)$=$24$。回到家后，Crash还在想着课上学的东西，为了研究最小公倍数，他画了一张$N\times M$...

【题目描述】小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。然而现在小 W 却记不起送给小X的是哪个数了。你能...