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 |
|
|
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 |