Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contest 339)

F - Product Equality

题目大意

• 给定N个整数A1,A2,…,AN。 找到满足以下条件的整数三元组(i,j,k)的数量：

  1≤i,j,k≤N Ai×Aj=Ak 1 ≤ N ≤ 1000 1 ≤ Ai < 10^1000

解题思路

• 很大，不能直接进行乘法计算

• 考虑哈希，取模变小

• 为保证结果的正确性，进行三哈希判断，都满足时为正确

• 注意" role="presentation" style="position: relative;">$$可以相等

  import java.io.*;
  import java.math.BigInteger;
  import java.util.Arrays;
  import java.util.BitSet;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.LinkedList;
  import java.util.PriorityQueue;
  import java.util.Queue;
  import java.util.Random;
  import java.util.StringTokenizer;
  import java.util.Vector;
   
   
   
   
  public class Main{
  	
  	public static void main(String[] args) throws IOException{
  		AReader input=new AReader();
  	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
   
  	    int n=input.nextInt();
  	    Random rd=new Random();
  	    BigInteger[] bm=new BigInteger[3];
  	    long[] lm=new long[3];
  	    for(int i=0;i<3;++i) {
  	    	lm[i]=BigInteger.probablePrime(31, rd).longValue();//mod为素数
  	    	bm[i]=BigInteger.valueOf(lm[i]);
  	    }
  	    long[] a=new long[n+1];
  	    long[] b=new long[n+1];
  	    long[] c=new long[n+1];
  	    HashMap hs1=new HashMap();
  	    HashMap hs2=new HashMap();
  	    HashMap hs3=new HashMap();
  	    HashMap Num=new HashMap();//A_i映射
  	    int[] num=new int[n+1];//统计相同A_i
  	    int cnt=0;
  	    for(int i=1;i<=n;++i){
  	    	BigInteger x=input.nextBigInteger();
  	    	a[i]=x.mod(bm[0]).longValue();
  	    	b[i]=x.mod(bm[1]).longValue();
  	    	c[i]=x.mod(bm[2]).longValue();
  	    	hs1.put(a[i], x);
  	    	hs2.put(b[i], x);
  	    	hs3.put(c[i], x);
  	    	if(Num.get(x)==null) {
  	    		cnt++;
  	    		Num.put(x, cnt);
  	    		num[cnt]=1;
  	    	}else {
  	    		num[Num.get(x)]++;
  	    	}
  	    }
  	    int ans=0;
  	    for(int i=1;i<=n;++i) {
  	    	for(int j=1;j<=n;++j) {
  	    		
  	    		BigInteger k1=hs1.get(a[i]*a[j]%lm[0]);
  	    		BigInteger k2=hs2.get(b[i]*b[j]%lm[1]);
  	    		BigInteger k3=hs3.get(c[i]*c[j]%lm[2]);
  	    		if(k1==null||k2==null||k3==null)continue;
  	    		
  	    		if(k1.equals(k2)&&k2.equals(k3)) {
  	    			int t=Num.get(k1);
  	    			ans+=num[t];
  	    		}
  	    	}
  	    }
  	    out.print(ans);			
   	    out.flush();
  	    out.close();
  	}
  	static
  	class AReader{
  	    BufferedReader bf;
  	    StringTokenizer st;
  	    BufferedWriter bw;
   
  	    public AReader(){
  	        bf=new BufferedReader(new InputStreamReader(System.in));
  	        st=new StringTokenizer("");
  	        bw=new BufferedWriter(new OutputStreamWriter(System.out));
  	    }
  	    public String nextLine() throws IOException{
  	        return bf.readLine();
  	    }
  	    public String next() throws IOException{
  	        while(!st.hasMoreTokens()){
  	            st=new StringTokenizer(bf.readLine());
  	        }
  	        return st.nextToken();
  	    }
  	    public char nextChar() throws IOException{
  	        //确定下一个token只有一个字符的时候再用
  	        return next().charAt(0);
  	    }
  	    public int nextInt() throws IOException{
  	        return Integer.parseInt(next());
  	    }
  	    public long nextLong() throws IOException{
  	        return Long.parseLong(next());
  	    }
  	    public double nextDouble() throws IOException{
  	        return Double.parseDouble(next());
  	    }
  	    public float nextFloat() throws IOException{
  	        return Float.parseFloat(next());
  	    }
  	    public byte nextByte() throws IOException{
  	        return Byte.parseByte(next());
  	    }
  	    public short nextShort() throws IOException{
  	        return Short.parseShort(next());
  	    }
  	    public BigInteger nextBigInteger() throws IOException{
  	        return new BigInteger(next());
  	    }
  	    public void println() throws IOException {
  	        bw.newLine();
  	    }
  	    public void println(int[] arr) throws IOException{
  	        for (int value : arr) {
  	            bw.write(value + " ");
  	        }
  	        println();
  	    }
  	    public void println(int l, int r, int[] arr) throws IOException{
  	        for (int i = l; i <= r; i ++) {
  	            bw.write(arr[i] + " ");
  	        }
  	        println();
  	    }
  	    public void println(int a) throws IOException{
  	        bw.write(String.valueOf(a));
  	        bw.newLine();
  	    }
  	    public void print(int a) throws IOException{
  	        bw.write(String.valueOf(a));
  	    }
  	    public void println(String a) throws IOException{
  	        bw.write(a);
  	        bw.newLine();
  	    }
  	    public void print(String a) throws IOException{
  	        bw.write(a);
  	    }
  	    public void println(long a) throws IOException{
  	        bw.write(String.valueOf(a));
  	        bw.newLine();
  	    }
  	    public void print(long a) throws IOException{
  	        bw.write(String.valueOf(a));
  	    }
  	    public void println(double a) throws IOException{
  	        bw.write(String.valueOf(a));
  	        bw.newLine();
  	    }
  	    public void print(double a) throws IOException{
  	        bw.write(String.valueOf(a));
  	    }
  	    public void print(char a) throws IOException{
  	        bw.write(String.valueOf(a));
  	    }
  	    public void println(char a) throws IOException{
  	        bw.write(String.valueOf(a));
  	        bw.newLine();
  	    }
  	}
  }