题目描述
给定一个长度为 n的正整数序列 x1,x2,…,xn。
请你回答 m个问题。
对于每个问题:
给定两个正整数 l,r(l≤r),用 S表示 [l,r]范围内的所有素数的集合,用 f(p)表示序列x1,x2,…,xn中能够被 p整除的元素的数量,请你计算并输出 ∑p∈Sf(p)的值。
输入格式
第一行包含整数 n。
第二行包含 n 个正整数 x1,x2,…,xn。
第三行包含整数 m。
接下来 m行,每行包含两个整数 l,r。
输出格式
共 m 行,每行输出一个问题的答案。
数据范围
前 4个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n≤106,2≤xi≤107,1≤m≤50000,2≤l≤r≤2×109。
算法1
思路:
1. 对于x数组中的每一个数y,计算出所有能够整除y的素数
2. 记录能够整除y(1中的)的素数z,z能整除x数组中的数的个数
3. 将z排序,使用前缀和累计答案
4. 对于每个l和r,找出小于l的最大素数,和小于等于r的最大素数(可以用二分或TreeMap),在z数组中相减就是答案
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {
static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
solve01();
pw.flush();
}
//计算素数,prime用于记录从小到大的素数,sprime用于记录素数,便于快速判断一个数是否是素数
static List<Integer> prime=new ArrayList<Integer>();
static Set<Integer> sprime=new HashSet<Integer>();
static {
int len=10000001;
boolean[] vis=new boolean[len];
for(int i=2;i<len;i++) {
for(long j=1l*i*i;j<len;j+=i) {
vis[(int)j]=true;
}
if(!vis[i]) {
prime.add(i);
sprime.add(i);
}
}
}
private static void solve01() throws IOException {
String[] s=br.readLine().split(" ");
int n=Integer.parseInt(s[0]);
int[] x=new int[n];
s=br.readLine().split(" ");
//记录每个素数能整除x数组中的数的个数,例如x[0]=12,recordprime={2=2,3=1}
Map<Integer, Integer> recordprime=new HashMap<Integer, Integer>();
//用于将x数组的数进行过滤,将相同的数记录出现的次数
Map<Integer,Integer> filter=new HashMap<Integer,Integer>();
for(int i=0;i<n;i++) {
x[i]=Integer.parseInt(s[i]);
filter.put(x[i], filter.getOrDefault(x[i], 0)+1);
}
for(int f:filter.keySet()) {
int y=f;
int count=filter.get(f);
for(int p:prime) {
//用set加快判断当前y是否是素数,如果是则直接退出
if(sprime.contains(y)) {
recordprime.put(y, recordprime.getOrDefault(y, 0)+count);
y=1;
break;
}
if(p>y) {
break;
}
//判断当前素数p是否能整除y
boolean re=false;
while(y%p==0) {
y/=p;
re=true;
}
if(re) {
recordprime.put(p, recordprime.getOrDefault(p, 0)+count);
}
}
if(y!=1) {
recordprime.put(y, recordprime.getOrDefault(y, 0)+count);
}
}
s=br.readLine().split(" ");
int m=Integer.parseInt(s[0]);
int size=recordprime.size();
int[][] tmp=new int[size][2];
int index=0;
//获取到能否整除x数组中的数的所有素数和给素数整除x数组中的数的个数,对应于下标0和1
for(int rp:recordprime.keySet()) {
tmp[index][0]=rp;
tmp[index][1]=recordprime.get(rp);
index++;
}
//按素数大小从小到大排序
Arrays.sort(tmp, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]>o2[0]) {
return 1;
}
return -1;
}
});
//使用前缀和,快速计算l,r范围内的素数整除x数组的数量
long[] tl=new long[size];
//对于每次输入的l和r,ts可以找到小于l的最大素数和小于等于r的最大素数
TreeMap<Integer, Integer> ts=new TreeMap<Integer, Integer>();
for(int i=0;i<size;i++) {
ts.put(tmp[i][0], i);
if(i==0) {
tl[i]=tmp[i][1];
continue;
}
tl[i]=tl[i-1]+tmp[i][1];
}
for(int i=0;i<m;i++) {
s=br.readLine().split(" ");
int l=Integer.parseInt(s[0]),r=Integer.parseInt(s[1]);
Integer ll=ts.floorKey(l-1),rr=ts.floorKey(r);
if(ll==null) {
if(rr==null) {
pw.println(0);
}
else {
pw.println(tl[ts.get(rr)]);
}
}
else {
pw.println(tl[ts.get(rr)]-tl[ts.get(ll)]);
}
}
}
}