D. Divide(math)[2021 ECNU Campus Invitational Contest]

题面如下：

题意简说：

求 ${\prod }_{i=l_2}^{r_2}\%{\prod }_{i=l_1}^{r_1}$ 是否 等于0

思路 or 题解：

$r_2!/(l_2-1)|r_1!/(l_1-1)!$
等价
$r_2!\ast (l_1-1)!==r_1!\ast (l_2-1)!$

判断$a|b$:
只要满足： 任意一个素数$p$， $a$包含$p$的数量 $\ge$ $b$ 包含 $p$ 的数量
就可以得出 $a|b$

官方题解

我们需要用线性筛去优化我们的代码

我们需要用前缀思想和去优化我们的代码

AC代码如下：

const int maxn = 10000009;
int prime[maxn];
bool sf[maxn];
int num = 0;
int a, b, x, y;
void sushu()
{
   sf[1] = 1;
   sf[0] = 1;
   for (int i = 2; i <= maxn; i++)
   {
       if (!sf[i])
           prime[++num] = i;
       for (int j = 1; j <= num; j++)
       {
           if (i * prime[j] > maxn)
               break;
           sf[i * prime[j]] = 1;
           if (i % prime[j] == 0)
               break;
       }
   }
}
int cal(int n, int p)
{
   int res = 0;
   while (n)
   {
       res += n / p;
       n /= p;
   }
   return res;
}
void solve()
{
   cin >> a >> b >> x >> y;
   for (int i = 1; i <= num; i++)
   {
       if (cal(y, prime[i]) - cal(x - 1, prime[i]) < cal(b, prime[i]) - cal(a - 1, prime[i]))
       {
           cout << "No\n";
           return ;
       }
   }
   cout << "Yes\n";
}
int main()
{
   buff;
   sushu();
   int _;
   cin >> _;
   while (_--)
       solve();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55