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...

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

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

Color[POJ2154]

【题目描述】一串项链上有$n$颗珠子,用$n$种颜色给它们染色(不一定都要用到),有多少种方案?通过已有方案进行旋转得到的染色方案不算。答案对$p$取模。 【输入格式】两个整数$n,p$。 【输出格式】一行一个整数表示总方案数模$p$。 $n\le 10^9$ 题解 $\operatorname{Burnside}$引理 设$A$和$B$为有限集合,$X$表示所有从$A$到$B$的映射集...