给定两组正整数 \(\{a,a+1,\cdots,b\}\) 和 \(\{c,c+1,\cdots,d\}\) 。判断 \(c·(c+1)\cdots d\) 能否被 \(a·(a+1)\cdots b\) 整除。
多测，有 \(t\) 组数据.
\(1\leq t\leq 10,1\leq a_i\leq b_i\leq10^7,1\leq c_i\leq d_i\leq 10^7\)
可以把数据离线下来 .
可以 \(O(v\log v)\) 地求出所有数的质因数及其个数 .
一个质因数一个质因数地考虑，当前考虑质数 \(p\)，设 \(cnt(i)\) 为 \(\prod i\) 中 \(p\) 的指数 .
那么，现在只需要判断 $cnt(d_i)-cnt(c_i-1) $ 与 \(cnt(b_i)-cnt(a_i-1)\) 的大小 .
但是，这样前缀和是 \(O(n^2)\) 地，发现只有 \(O(\frac{v}{p})\) 个位置是有用的 .
这样，就可以 \(O(v\log v+tn)\) 地判断出所有询问.
时间复杂度 : \(O(v\log v+tn)\)
空间复杂度 : \(O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
int t;
int a[12],b[12],c[12],d[12];
bool ok[12];
bool p[10000010];
int cnt[10000010];
int get_cnt(int x,int y,int k){
int mx=10000000/k*k;
return cnt[min(x/k*k,mx)]-cnt[min(((y+k-1)/k-1)*k,mx)];
}
int main(){
t=read();
for(int i=0;i<t;i++){
a[i]=read();
b[i]=read();
c[i]=read();
d[i]=read();
}
memset(p,true,sizeof(p));
p[0]=p[1]=false;
for(int i=2;i<=10000000;i++){
if(1ll*i*i>=10000000)break;
if(!p[i])continue;
for(int j=i*i;j<=10000000;j+=i)p[j]=false;
}
memset(ok,true,sizeof(ok));
for(int i=2;i<=10000000;i++){
if(!p[i])continue;
cnt[0]=0;
for(int j=i;j<=10000000;j+=i){
int tmp=j,sum=0;
while(tmp%i==0){
sum++;
tmp/=i;
}
cnt[j]=sum+cnt[j-i];
}
for(int j=0;j<t;j++){
if(get_cnt(d[j],c[j],i)<get_cnt(b[j],a[j],i))
ok[j]=false;
}
}
for(int i=0;i<t;i++){
if(ok[i])puts("DA");
else puts("NE");
}
return 0;
}
/*inline? ll or int? size? min max?*/