No.2187 三立法和 mod 333
タグ : / 解いたユーザー数 43
作問者 : 👑
p-adic
/ テスター :
testestest
注意
この問題は実行時間制限が100msです。
問題文
入力に正整数 $A$ が与えられます。
$2$ 条件
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle x^3 + y^3 + z^3 &\displaystyle \equiv &\displaystyle A \pmod{333} \\ \displaystyle x^4 + y^4 + z^4 &\displaystyle \leq &\displaystyle 4444^4 \end{array} \right. $
を全て満たす正整数の $3$ つ組 $(x,y,z)$ の総数を求めてください。
入力
入力は次の形式で標準入力から与えられます：
$A$
制約
入力は以下の制約を満たします：
- $A$ は $333$ 以下の正整数
出力
$2$ 条件
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle x^3 + y^3 + z^3 &\displaystyle \equiv &\displaystyle A \pmod{333} \\ \displaystyle x^4 + y^4 + z^4 &\displaystyle \leq &\displaystyle 4444^4 \end{array} \right. $
を全て満たす正整数の $3$ つ組 $(x,y,z)$ の総数を $1$ 行に出力してください。
ただしそのような $(x,y,z)$ の個数は有限個であることが知られています。
最後に改行してください。
サンプル
サンプル1
入力
3
出力
65944976
$2$ 条件
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle x^3 + y^3 + z^3 &\displaystyle \equiv &\displaystyle 3 \pmod{333} \\ \displaystyle x^4 + y^4 + z^4 &\displaystyle \leq &\displaystyle 4444^4 \end{array} \right. $
を全て満たす正整数の $3$ つ組 $(x,y,z)$ の例には $(1,1,1)$ があります。そのような $(x,y,z)$ の総数は $65944976$ 個です。
サンプル2
入力
4
出力
0
$2$ 条件
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle x^3 + y^3 + z^3 &\displaystyle \equiv &\displaystyle 4 \pmod{333} \\ \displaystyle x^4 + y^4 + z^4 &\displaystyle \leq &\displaystyle 4444^4 \end{array} \right. $
を全て満たす正整数の $3$ つ組 $(x,y,z)$ は存在しません。何故ならば、$333$ は $9$ の倍数であるので $1$ つ目の条件から $x^3 +y^3 + z^3 \equiv 4 \pmod{9}$ であることが従いますが、立方数を $9$ で割った余りは $0, 1, 8$ の $3$ 通りしかなく、これらから重複を込めて $3$ 数をどう選んで足し合わせても法 $9$ で $4$ に一致しないからです。
サンプル3
入力
10
出力
499924557
$2$ 条件
$\displaystyle \left\{ \begin{array}{rcl} \displaystyle x^3 + y^3 + z^3 &\displaystyle \equiv &\displaystyle 10 \pmod{333} \\ \displaystyle x^4 + y^4 + z^4 &\displaystyle \leq &\displaystyle 4444^4 \end{array} \right. $
を全て満たす正整数の $3$ つ組 $(x,y,z)$ の例には $(2,1,1)$ や $(1,2,1)$ や $(1,1,2)$ があります。そのような $(x,y,z)$ の総数は $499924557$ 個です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。