Submission #3586820


Source Code Expand

#include<map>
#include<set>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#include<complex>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll> 
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end()) 
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>=x;i--)
typedef long long ll;
using namespace std;

 
/*
struct point
{
long long dist; long long name;
bool operator<(const point& rhs) const {
return dist > rhs.dist;
}
};
*/


vll v;

void alldiv(ll k) {
	for (ll i = 1; i * i<= k; i++) {
		if (k%i == 0) {
			v.push_back(i);
			if (i*i != k) {
				v.push_back(k / i);
			}
		}
	}
	sort(v.begin(), v.end());
}

ll gcd(ll x, ll y) {
	if (y == 0) {
		return x;
	}
	else {
		return gcd(y, x%y);
	}
}

map<ll, ll> mp;

int main() {
	ll n, k;
	cin >> n >> k;
	alldiv(k);
	REP(i, 1, n) {
		ll t;
		cin >> t;
		mp[gcd(t, k)]++;
	}
	ll ans = 0;
	REP(i, 0, SIZE(v) - 1) {
		REP(j, i + 1, SIZE(v) - 1) {
			if (v[i] * v[j] % k == 0) {
				ans += mp[v[i]] * mp[v[j]];
			}
		}
	}
	REP(i, 0, SIZE(v) - 1) {
		ll t = mp[v[i]];
		if (v[i] * v[i] % k == 0) {
			ans += t * (t - 1) / 2;
		}
	}
	cout << ans << endl;
}

/*
ll const MAX = 300;
ll a[MAX][MAX];
ll w, h;
ll sym[5] = {};

void check(ll i, ll j) {
	ll symi = h - i + 1;
	ll symj = w - j + 1;
	ll p1, p2, p3, p4;
	p1 = a[i][j]; p2 = a[symi][j]; p3 = a[symi][symj]; p4 = a[i][symj];
	if (p1&&p2&&p3&&p4) {
		sym[3]++;
	}
	else if ((p1&&p4) || (p2&&p3)) {
		sym[2]++;
	}
	else if ((p1&&p2) || (p3&&p4)) {
		sym[1]++;
	}
	else if (p1 || p2 || p3 || p4) {
		sym[0]++;
	}
}

//1 tate ; 2 yoko

int main() {
	cin >> h >> w;
	ll tate, yoko;
	cin >> tate >> yoko;
	REP(i, 1, h) {
		REP(j, 1, w) {
			char c;
			cin >> c;
			a[i][j] = (c == 'S');
		}
	}
	REP(i, 1, h / 2) {
		REP(j, 1, w / 2) {
			check(i, j);
		}
	}
	if (sym[1] == sym[2] && sym[2] == sym[3] && sym[3] == 0) {
		cout << tate + yoko << endl;
		return 0;
	}
	if (sym[3] != 0) {
		ll pt = sym[3] * (tate + yoko + max(tate, yoko));
		if (sym[1] == 0 && sym[2] == 0 && sym[0] == 0) {
			pt -= tate + yoko;
			cout << pt << endl;
			return 0;
		}
		else {
			ll pt1 = max(ll(0),tate * (sym[1] - 1));
			if (sym[0] + sym[2] == 0) {
				pt1 -= tate;
			}
			ll pt2 = max(ll(0),yoko * (sym[2] - 1));
			if (sym[0] + sym[1] == 0) {
				pt2 -= yoko;
			}
			pt += max(pt1, pt2);
			cout << pt + tate + yoko << endl;
			return 0;
		}
	}
	else {
		ll pt1 = max(ll(0), tate * (sym[1] - 1));
		if (sym[0] + sym[2] == 0) {
			pt1 -= tate;
		}
		ll pt2 = max(ll(0), yoko * (sym[2] - 1));
		if (sym[0] + sym[1] == 0) {
			pt2 -= yoko;
		}
		ll pt = max(pt1, pt2);
		cout << pt + tate + yoko << endl;
		return 0;
	}
}
*/

Submission Info

Submission Time
Task C - ロト2
User nejineji
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3067 Byte
Status AC
Exec Time 115 ms
Memory 384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 25
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 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
Case Name Status Exec Time Memory
00_example_01.txt AC 1 ms 256 KB
00_example_02.txt AC 1 ms 256 KB
00_example_03.txt AC 1 ms 256 KB
10_random_01.txt AC 1 ms 256 KB
10_random_02.txt AC 1 ms 256 KB
10_random_03.txt AC 1 ms 256 KB
10_random_04.txt AC 1 ms 256 KB
10_random_05.txt AC 1 ms 256 KB
20_max_01.txt AC 73 ms 256 KB
20_max_02.txt AC 70 ms 256 KB
20_max_03.txt AC 90 ms 256 KB
20_max_04.txt AC 70 ms 256 KB
20_max_05.txt AC 104 ms 256 KB
30_overflow_01.txt AC 66 ms 256 KB
30_overflow_02.txt AC 66 ms 256 KB
40_dmax_01.txt AC 115 ms 384 KB
40_dmax_02.txt AC 115 ms 384 KB
40_dmax_03.txt AC 115 ms 384 KB
50_prime_01.txt AC 72 ms 256 KB
50_prime_02.txt AC 81 ms 256 KB
50_prime_03.txt AC 91 ms 256 KB
60_prime_pow_01.txt AC 96 ms 256 KB
60_prime_pow_02.txt AC 89 ms 256 KB
60_prime_pow_03.txt AC 89 ms 256 KB
70_one_01.txt AC 58 ms 256 KB