torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

数学

AtCoder Beginner Contest 342, D : Square Pair

問題文 https://atcoder.jp/contests/abc342/tasks/abc342_d 問題概要 $n$ 項からなる非負自然数の列 $\langle A_1, A_2, \dots, A_n \rangle$ が与えられる.以下の条件を満たす順序対 $( i, j )$ はいくつあるか? $1 \leq i $A_i A_j$ は平方数 制約 $2 \…

AtCoder Beginner Contest 340, F : S = 1

問題文 https://atcoder.jp/contests/abc340/tasks/abc340_f 問題概要 整数 $x, y$ ($x \neq 0$ or $y \neq 0$) が与えられる. 以下の条件を満たす整数 $a, b$ を出力せよ. $-10^{ 18 } \leq a, b \leq 10^{ 18 }$ 二次元平面 $\mathbb R^2$ 上の点 $( 0, …

AtCoder Beginner Contest 172, D : Sum of Divisors

問題文 https://atcoder.jp/contests/abc172/tasks/abc172_d 問題概要 正整数 $X$ について,関数 $f$ を $f( X ) = $ $X$ の約数の個数 とする. 正整数 $N$ が与えられるので,$$\sum_{ K = 1 }^{ N } K \times f( K )$$ を求めよ 制約 $1 \leq N \leq 10^…

AtCoder Beginner Contest 169, D : Div Game

問題文 https://atcoder.jp/contests/abc169/tasks/abc169_d 問題概要 正整数 $N$ が与えられる.$N$ に対し,以下の一連の操作を繰り返し行うことを考える. 以下の条件を満たす整数 $z$ を選ぶ ある素数 $p$ と正整数 $e$ で $p^e$ と書ける $z \mid N$ で…

AtCoder Beginner Contest 168, C : : (Colon)

問題文 https://atcoder.jp/contests/abc168/tasks/abc168_c 問題概要 長針の長さが $A$ ,短針の長さが $B$ で,$H$ 時 $M $ 分を指しているアナログ時計を考える(針は等角速度で運動する). 2 つの針の先端同士の距離を求めよ. 制約 $1 \leq A, B \leq …

AtCoder Beginner Contest 167, E : Colorful Blocks

問題文 https://atcoder.jp/contests/abc167/tasks/abc167_e 問題概要 正整数 $N, M, K$ が与えられる. 最初,$N$ 個のブロックが横一列に(隣接して)並んでいる.このブロックたちに色を塗りたい.次の条件を満たす色の塗り方を $\pmod{ 998244353 }$ で…

AtCoder Beginner Contest 165, D: Floor Function

問題文 https://atcoder.jp/contests/abc165/tasks/abc165_d 問題概要 正整数 $A, B, N$ が与えられる.$\mathrm{ floor }\left( \frac{ A x } B \right) - A ~ \mathrm{ floor }\left( \frac x B \right)$ の最大値を求めよ 制約 $1 \leq A \leq 10^6$ $1 \…

AtCoder Beginner Contest 166, D : I hate Factorization

問題文 https://atcoder.jp/contests/abc166/tasks/abc166_d 問題概要 正整数 $X$ が与えられる.$A^5 - B^5 = X$ となる整数 $A, B$ の組を一つ示せ.なお,解が存在するような $X$ のみが与えられる. 制約 $1 \leq X \leq 10^9$

GCDLCM2

問題文 https://community.topcoder.com/stat?c=problem_statement&pm=14169 問題概要 正整数の配列が与えられる.この配列に対し,以下の操作を任意回行う. 2 つの要素 $x, y$ を選ぶ $x, y$ を削除する $\mathit{ GCD }( x, y ), \mathit{ LCM }( x, y )$…

Codeforces 323, Division 1, A ( Division 2, C ) - GCD Table

問題文 http://codeforces.com/contest/583/problem/C 問題概要 $n$ 要素の数列 $a$ から生成されるGCD Table を,$$g_{ ij } = \mathrm{ gcd }( a_i, a_j )$$ なる $n \times n$ 行列とする. 今,$g$ の要素を適当に並び替えた $n \times n$ 個の整数が与…