题解 | #因子区间#

``` java []
import java.io.*;
import java.util.*;

public class Main {
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception {
        int n=Int();
        int q=Int();
        int[] a=new int[n+1];
        int[]b=new int[n+1];
        for(int i=1;i<=n;i++){
            a[i]=Int();
        }
        for(int i=1;i<=n;i++){
            int x=a[i];
            for(int j=1;j<=Math.sqrt(x);j++){
                if(x%j==0){
                    b[i]+=2;
                }
                if(j==Math.sqrt(x)&&j*j==x){
                    b[i]--;
                }
            }
        }
        HashMap<Integer,Long>[]hp=new HashMap[n+1];
        for(int i=0;i<=n;i++){
            hp[i]=new HashMap<>();
        }
        for(int i=1;i<=n;i++){
            hp[i].put(b[i],hp[i].getOrDefault(b[i],0l)+1);
            for(Map.Entry<Integer,Long> l:hp[i-1].entrySet()){
                hp[i].put(l.getKey(),l.getValue()+hp[i].getOrDefault(l.getKey(),0l));
            }
        }
        while(q-->0){
            int l=Int();
            int r=Int();
            long ans=0;
            for(Map.Entry<Integer,Long> l1:hp[r].entrySet()){
                if(hp[l-1].containsKey(l1.getKey())){
                    ans+=(l1.getValue()-hp[l-1].get(l1.getKey()))*(l1.getValue()-hp[l-1].get(l1.getKey())-1)/2;
                }
                else {
                    ans+= l1.getValue()*(l1.getValue()-1)/2;
                }
            }
            pw.println(ans);
        }
        pw.flush();
    }
    public static String Line() throws Exception {
        String s = bf.readLine();
        return s;
    }

    public static int Int() throws Exception {
        st.nextToken();
        return (int) st.nval;

    }

    public static long Long() throws Exception {
        st.nextToken();
        return (long) st.nval;

    }

    public static double Double() throws Exception {
        st.nextToken();
        return st.nval;

    }

}

为什么map的value改成long就过了因子数不是最多1e5吗