DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選

Submission #7889027

Source codeソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.*;
 
public class Main  {
	static long MOD=1000000000+7;
	static long ans=0;
	public static void main(String[] args){
		PrintWriter out = new PrintWriter(System.out);
		InputReader sc=new InputReader(System.in);
		 int N=sc.nextInt();
		 long K=sc.nextLong();
		 long[] A=sc.nextLongArray(N);
		 HashMap<Long, Long> hashMap=new HashMap<>();
		 for (int i = 0; i < A.length; i++) {
			A[i]=gcd(A[i], K);
			if (!hashMap.containsKey(A[i])) {
				hashMap.put(A[i], 1L);
			}
			else {
				hashMap.put(A[i], hashMap.get(A[i])+1);
			}
		}
		 long ans=0;
		 for (long l : hashMap.keySet()) {
			for (long m : hashMap.keySet()) {
				long x=hashMap.get(l);
				long y=hashMap.get(m);
				if ((l*m)%K!=0) {
					continue;
				}
				if (l==m) {
					ans+=(x-1)*x/2;
				}
				else if (l>m) {
					ans+=x*y;
				}
			}
		}
		System.out.println(ans);
 	}
	 static long ceil(long a,long b){
	        return a%b==0?a/b:a/b+1;
	    }
	 static long gcd(long a,long b) {
			if (b==0) {
				return a;
			}
			return gcd(b,a%b);
		}
	static class InputReader { 
		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;
 
		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}
 
		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}
 
		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}
 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
 
		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}
 
		public boolean hasNext() {
			skip();
			return hasNextByte();
		}
 
		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
 
		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public double nextDouble() {
			return Double.parseDouble(next());
		}
 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
 
		public char[][] nextCharMap(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++)
				map[i] = next().toCharArray();
			return map;
		}
	}
}

Submission

Task問題 C - ロト2
User nameユーザ名 bouperson
Created time投稿日時
Language言語 Java8 (OpenJDK 1.8.0)
Status状態 AC
Score得点 400
Source lengthソースコード長 3868 Byte
File nameファイル名
Exec time実行時間 340 ms
Memory usageメモリ使用量 63760 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_example_01.txt,00_example_02.txt,00_example_03.txt
All 400 / 400 00_example_01.txt,00_example_02.txt,00_example_03.txt,10_random_01.txt,10_random_02.txt,10_random_03.txt,10_random_04.txt,10_random_05.txt,20_max_01.txt,20_max_02.txt,20_max_03.txt,20_max_04.txt,20_max_05.txt,30_overflow_01.txt,30_overflow_02.txt,40_dmax_01.txt,40_dmax_02.txt,40_dmax_03.txt,50_prime_01.txt,50_prime_02.txt,50_prime_03.txt,60_prime_pow_01.txt,60_prime_pow_02.txt,60_prime_pow_03.txt,70_one_01.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_example_01.txt AC 78 ms 21204 KB
00_example_02.txt AC 71 ms 19156 KB
00_example_03.txt AC 72 ms 19796 KB
10_random_01.txt AC 75 ms 22868 KB
10_random_02.txt AC 76 ms 19668 KB
10_random_03.txt AC 73 ms 20948 KB
10_random_04.txt AC 74 ms 20948 KB
10_random_05.txt AC 77 ms 18900 KB
20_max_01.txt AC 181 ms 31604 KB
20_max_02.txt AC 176 ms 35256 KB
20_max_03.txt AC 195 ms 38984 KB
20_max_04.txt AC 167 ms 26884 KB
20_max_05.txt AC 181 ms 29648 KB
30_overflow_01.txt AC 167 ms 26116 KB
30_overflow_02.txt AC 174 ms 26324 KB
40_dmax_01.txt AC 340 ms 60408 KB
40_dmax_02.txt AC 334 ms 59232 KB
40_dmax_03.txt AC 335 ms 63760 KB
50_prime_01.txt AC 179 ms 33280 KB
50_prime_02.txt AC 181 ms 32592 KB
50_prime_03.txt AC 186 ms 40000 KB
60_prime_pow_01.txt AC 205 ms 42240 KB
60_prime_pow_02.txt AC 197 ms 40136 KB
60_prime_pow_03.txt AC 193 ms 38988 KB
70_one_01.txt AC 162 ms 25708 KB