Submission #968304

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}
	Scanner cin;
	const int MOD = 1000000007;
	const int INF = int.MaxValue;
	const long INFL = long.MaxValue;
	const double EPS = 1e-7;
	const double PI = 3.1415926536;

	int[] p = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 };

	int MAX = 1000000000;

	void prog()
	{
		cin = new Scanner();
		int[,] dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
		int[,] dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

		int N = cin.nextInt();
		int K = cin.nextInt();
		int[] A = new int[N];
		Dictionary<int, int> dict = new Dictionary<int, int>();
		long ans = 0;
		for (int i = 0; i < N; i++)
		{
			A[i] = Gcd(cin.nextInt(), K);
		}
		for (int i = 0; i < N; i++)
		{
			if (dict.ContainsKey(A[i]))
			{
				dict[A[i]]++;
			}
			else
			{
				dict.Add(A[i], 1);
			}
		}
		IOrderedEnumerable<Pair> en = dict.OrderBy(_ => _.Key);
		foreach(var a in en)
		{
			foreach (var b in en)
			{
				if (b.Key < a.Key) continue;
				else if ((long)a.Key * b.Key % K == 0)
				{
					if (a.Key == b.Key)
					{
						ans += (long)a.Value * (a.Value - 1) / 2;
					}
					else
					{
						ans += (long)a.Value * b.Value;
					}
				}
			}
		}
		Console.WriteLine(ans);
	}

	// 最大公約数
	int Gcd(int a, int b)
	{
		if (b == 0) return a;
		else return Gcd(b, a % b);
	}
}

class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		i = 0;
		return next();
	}

	public int nextInt()
	{
		return int.Parse(next());
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}
}

Submission Info

Judge Result