Problem b[HAOI2011]

题目描述对于给出的$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的数字表格

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

完全平方数[中山市选2011]

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