Submission #3547535
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define pb push_back
#define fill(x, y) memset(x, y, sizeof(x))
#define even(x) x % 2 == 0
#define odd(x) x % 2 != 0
#define all(x) x.begin(), x.end()
#define pcnt __builtin_popcount
#define buli(x) __builtin_popcountll(x)
#define F first
#define S second
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define IN1(x) ll x; cin >> x;
// these functions return the position of result of Binary Search.
#define LB(s, t, x) (int) (lower_bound(s, t, x) - s)
#define UB(s, t, x) (int) (upper_bound(s, t, x) - s)
ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b >>= 1); return ans; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp ? (a / temp * b) : 0; }
int mDays[] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dx8[] = { 1, -1, 0, 0, 1, 1, -1, -1 }, dy8[] = { 0, 0, -1, 1, -1, 1, -1, 1 };
template <typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template <typename T, typename... Ts>
auto make_v(size_t a, size_t b, Ts... ts) { return vector<decltype(make_v<T>(b, ts...))>(a, make_v<T>(b, ts...)); }
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }
// auto dp = make_v<int>(4, h, w);
// fill_v(dp, 0);
const ll INF_LL = (1ll << 60);
const int INF_INT = (int)1e9;
const ll MOD_CONST = (ll)(1e9 + 7);
template <typename T>
vector<T> pows(int b, int n) {
vector<T> ret;
T x = 1;
while (ret.size() < n) {
ret.push_back(x);
x *= b;
}
return ret;
}
// find string "from" in "str", and replace them to "to"
void strReplace(std::string& str, const std::string& from, const std::string& to) {
std::string::size_type pos = 0;
while (pos = str.find(from, pos), pos != std::string::npos) {
str.replace(pos, from.length(), to);
pos += to.length();
}
}
template <class T>
bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T>
bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
inline tuple<ll, ll> rotate45(tuple<ll, ll> point) { ll x = get<0>(point), y = get<1>(point); return tuple<ll, ll>(x + y, x - y); }
inline bool rangeCheck2D(int nx, int ny, int Width, int Height) { return nx >= 0 and nx < Width and ny >= 0 and ny < Height; }
template <typename T>
vector<T> INPA(ll n) {
vector<T> x;
REP(i, n) {
T tmp; cin >> tmp;
x.push_back(tmp);
}
return move(x);
}
template <typename T>
void out(T o) { cout << o << endl; }
template <typename T>
void out(vector<T> &out) { REP(i, (int)out.size()) { cout << out[i]; if (i == (int)out.size() - 1) cout << endl; else cout << " "; } }
template <typename T>
void out(vector<vector<T>> o) { REP(i, o.size()) out(o[i]); }
void YesNo(bool f) { cout << (f?"Yes":"No") << endl; }
void YESNO(bool f) { cout << (f?"YES":"NO") << endl; }
// use " for (const auto& e : V)
int main(void)
{
cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20);
IN1(N); IN1(K);
auto a = INPA<ll>(N);
if (K == 1) {
ll ans = 0;
REP(i, N-1) ans += i + 1;
out(ans);
return 0;
}
map<ll, ll> cnt;
for (int i = 0; i < a.size(); ++i) {
cnt[gcd(K, a[i])]++;
}
ll ans = 0;
for (auto&& i : cnt) {
for (auto&& j : cnt) {
if ((i.first * j.first) % K == 0) {
if (i.first == j.first)
ans += i.second * (j.second - 1);
else
ans += i.second * j.second;
}
}
}
out((ans + 1) / 2);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ロト2 |
User |
xoke |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
4078 Byte |
Status |
AC |
Exec Time |
79 ms |
Memory |
2420 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 |
35 ms |
2420 KB |
20_max_02.txt |
AC |
33 ms |
2420 KB |
20_max_03.txt |
AC |
43 ms |
2420 KB |
20_max_04.txt |
AC |
33 ms |
2420 KB |
20_max_05.txt |
AC |
50 ms |
2420 KB |
30_overflow_01.txt |
AC |
32 ms |
2420 KB |
30_overflow_02.txt |
AC |
32 ms |
2420 KB |
40_dmax_01.txt |
AC |
79 ms |
2420 KB |
40_dmax_02.txt |
AC |
78 ms |
2420 KB |
40_dmax_03.txt |
AC |
78 ms |
2420 KB |
50_prime_01.txt |
AC |
34 ms |
2420 KB |
50_prime_02.txt |
AC |
38 ms |
2420 KB |
50_prime_03.txt |
AC |
41 ms |
2420 KB |
60_prime_pow_01.txt |
AC |
42 ms |
2420 KB |
60_prime_pow_02.txt |
AC |
42 ms |
2420 KB |
60_prime_pow_03.txt |
AC |
40 ms |
2420 KB |
70_one_01.txt |
AC |
20 ms |
2420 KB |