与GCD有关的题目

Posted on By 二价氢

#GCD

这一类题大多是这样的……

给定,求的解的组数(BZOJ 1101,BZOJ 2190)

同时有很多组变形

  1. 给定,求的解的组数(BZOJ 2301)
  2. 给定,求质数的解的组数(BZOJ 2818,BZOJ 2820)

#莫比乌斯函数

利用这个东西,我们能通过筛法很快地求出

\(\mu(0)\) = 1
for i := 2\(\rightarrow\)n :
    if i is a prime:
        for j:= 2i \(\rightarrow\) n,step = i:
            j is not a prime
            if \(\left\lfloor{\frac{j}{i}}\right\rfloor\ \mathrm{mod}\ i = 0\):
                \(\mu(j)\)=0
            else
                \(\mu(j)\)=\(-\mu(\left\lfloor{\frac{j}{i}}\right\rfloor)\)

由莫比乌斯反演,我们得到:

对于给定的,设表示满足的数量

则有

然后根据和式的分配率就能得到对于的结果了

诶,上面那几题就没啥区别了囧

对于第二种变形……我再想想