[COCI2020-2021#4] Vepar
题意
给定两组正整数 \(a,a+1,\ldots,b\) 和 \(c,c+1,\ldots,d\)。判断 \(c\times(c+1)\times\ldots\times d\) 能否被 \(a\times (a + 1)\times \ldots\times b\) 整除。
思路
将 \(c\times(c+1)\times\ldots\times d\) 转化为 \(\frac{d!}{(c-1)!}\)。
将 \(a\times (a + 1)\times \ldots\times b\) 转化为 \(\frac{b!}{(a-1)!}\)。
题意转化为 \(\frac{d!(a-1)!}{b!(c-1)!}\) 是否为整数。
使用阶乘分解这道题的做法把分子分母分别分解质因数，判断即可。
以下是阶乘分解的做法：
考虑质数 \(x\) 在 \(a!\) 中出现了多少次。
答案为 \(\sum \lfloor \frac{a}{x^k} \rfloor\)。
因为 \(x\) 在所有 \(x\) 的倍数中出现了一次，在 \(x^2\) 的倍数中出现了两次。
而 \(x^2\) 的倍数也是 \(x\) 的倍数，已经统计了一遍，所以只用再统计一遍。
其它同理。
时间复杂度：\(O(\frac{n}{\log n}) \times O(\log_n)=O(n)\)。
代码
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N = 1e7 + 5;
int pr[N], cnt, id[N];
bool is[N];
void pri() {
for (int i = 2; i <= 1e7; i ++) {
if (!is[i]) pr[++ cnt] = i, id[i] = cnt;
for (int j = 1; j <= cnt && i * pr[j] <= 1e7; j ++) {
is[i * pr[j]] = 1;
if (i % pr[j] == 0) break;
}
}
}
void get(int n, int* c, int v) {
ll k, ans;
for(int i=1;i<=cnt;i++)
{
k=pr[i];
ans=0;
while(k<=n) {
ans+=(n/k);
k *= pr[i];
}
c[i] += ans * v;
}
}
int c1[N], c2[N];
void solve() {
int a, b, c, d;
cin >> c >> d >> a >> b;
get(d, c1, 1); get(a - 1, c1, 1);
get(c - 1, c2, 1); get(b, c2, 1);
bool ok = 1;
for (int i = 1; i <= cnt; i ++)
if (c2[i] < c1[i]) ok = 0;
if (ok) cout << "DA\n";
else cout << "NE\n";
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
pri();
int T = 1;
cin >> T;
while (T --)
solve();
return 0;
}