题解 P7281

· · 题解

题目传送门

Description

给定两组正整数 \{a,a+1,\cdots,b\} 和 \{c,c+1,\cdots,d\}。判断 c·(c+1)\cdots d 能否被 a·(a+1)\cdots b 整除。

Analyse

为了描述方便，令 x=a·(a+1)\cdots b，y=c·(c+1)\cdots d。

对于整除类的题目，容易想到当 x\%y=0 时，对于每个在 y 中出现的质因数 p 必在 x 中出现，且在 x 中出现次数更多。那么我们可以对 x 和 y 进行分解质因数，然后计算质因数 p 出现次数并比较。

对于本题，由于 x 为多数相乘，且范围较大，考虑通过计算出质因子 p 在 b! 中出现的次数和在 a-1 中出现的次数。那么将两者相减就是 p 在 x 中出现的次数。为了方便枚举质因子，这里用欧拉筛法将所有质数线性筛出。

Pay~attention

注意到 n! 中质因子 p 的数量等于 1\sim n 中 p 的数量和。

证明：（摘自 网络）

在 1\sim n 中，p 的倍数，即至少包含 1 个质因子 p 的有 \lfloor \frac{n}{p} \rfloor 个。

而 p^2 的倍数，即至少包含 2 个质因子 p 的有 \lfloor \frac{n}{p^2}\rfloor 个。但其中至少包含 1 个质因子已经在 \lfloor \frac{n}{p} \rfloor 里统计过，所以只需要再统计第 2 个质因子，即累加上 \lfloor \frac{n}{p^2}\rfloor，而不是 2 \times \lfloor \frac{n}{p^2}\rfloor。

综上所述，n ! 中质因子 p 的个数为：

\lfloor \frac{n}{p}\rfloor+\lfloor \frac{n}{p^2}\rfloor+\lfloor \frac{n}{p^3}\rfloor+\lfloor \frac{n}{p^{\lfloor{\log_p} n\rfloor}}\rfloor=\sum\limits_{p^k\le n}{\lfloor \frac{n}{p^k}\rfloor} Solution

欧拉筛法部分是板子，此处就不放了。

计算质因子出现次数部分如下：

int count(int x,int a)
{
    int sum=0;
    while(x)
    {
        sum+=x/a;
        x/=a;
    }
    return sum;
}

判断整除部分如下：

for(int i=1;i<=cnt&&pri[i]<=b;i++)
{
    int a_b=count(b,pri[i])-count(a-1,pri[i]);
    int c_d=count(d,pri[i])-count(c-1,pri[i]);
    if(a_b>c_d)
    {
        sol=false;
        break;
    }
}
The~end

客官看完别忘了点个赞哦~