ABC 342
Table of Contents
https://atcoder.jp/contests/abc342
A. Yay
https://atcoder.jp/contests/abc342/tasks/abc342_a
B. Which is ahead?
https://atcoder.jp/contests/abc342/tasks/abc342_b
C. Many Replacement
https://atcoder.jp/contests/abc342/tasks/abc342_c
D. Square Pair
https://atcoder.jp/contests/abc342/tasks/abc342_d
2026/1/17 自力 AC
$A_i$ が $0$ のとき
任意の $A_j$ と組にできる。 $0$ の個数を $X$ とすると、$A_i = 0 \text{ or } A_j = 0$ 組の数は $X(X-1)/2 + X(N-X)$ である。
$A_i \neq 0$ であるときを考える
$A_i = \prod_{k} p_{k}^{r_k}$ とするとき、 $A_i A_j$ が平方数であるための必要十分条件は、 全ての $k$ において $A_i$, $A_j$ の $r_k$ の偶奇が等しいことである。
$A_i$ の各素因数の指数を $\mod 2$ で見たときの情報だけを持つ数 $B_i$ を考える。 すなわち、 $B_i = \prod_{k} p_{k}^{r_k \mod 2}$ とする。
$B_i = B_j$ となる $i < j$ を選べば $A_i A_j$ が平方数となるので $C = B_i$ となる $i$ の個数を $M$ とすると組の個数は $M(M-1)/2$ である。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
int m = (ll)2e+5 + 5;
vll sieve(m, 1);
iota(all(sieve), 0);
sieve[0] = sieve[1] = 1;
rep2(i, 2, m) {
for (ll j = i + i; j < m; j += i) {
chmin(sieve[j], i);
}
}
auto f = [&](ll x) -> ll {
ll ret = 1;
while (x != 1) {
ll d = sieve[x];
ll cnt = 0;
while (x % d == 0) {
cnt++;
x /= d;
}
if (cnt & 1) ret *= d;
}
return ret;
};
ll nzero = 0;
map<ll, ll> mp;
rep(i, N) {
if (A[i] == 0) {
nzero++;
} else {
mp[f(A[i])]++;
}
}
ll ans = nzero * (nzero - 1) / 2;
ans += nzero * (N - nzero);
for (auto [k, v] : mp) {
ans += v * (v - 1) / 2;
}
cout << ans << endl;
}
E. Last Train
https://atcoder.jp/contests/abc342/tasks/abc342_e
F. Black Jack
https://atcoder.jp/contests/abc342/tasks/abc342_f