問題一覧 > 教育的問題

No.2187 三立法和 mod 333

レベル : / 実行時間制限 : 1ケース 0.100秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 44
作問者 : 👑 p-adic / テスター : 👑 testestest
0 ProblemId : 8805 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-01-13 21:47:43

注意

この問題は実行時間制限が100msです。

問題文

入力に正整数 AA が与えられます。

　

22 条件

{x3+y3+z3≡A(mod333)x4+y4+z4≤44444\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.

を全て満たす正整数の 33 つ組 (x,y,z)(x,y,z) の総数を求めてください。

入力

入力は次の形式で標準入力から与えられます： 

AA

制約

入力は以下の制約を満たします：

  • AA は 333333 以下の正整数

出力

22 条件

{x3+y3+z3≡A(mod333)x4+y4+z4≤44444\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.

を全て満たす正整数の 33 つ組 (x,y,z)(x,y,z) の総数を 11 行に出力してください。

ただしそのような (x,y,z)(x,y,z) の個数は有限個であることが知られています。

最後に改行してください。

サンプル

サンプル1
入力
3
出力
65944976

22 条件

{x3+y3+z3≡3(mod333)x4+y4+z4≤44444\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.

を全て満たす正整数の 33 つ組 (x,y,z)(x,y,z) の例には (1,1,1)(1,1,1) があります。そのような (x,y,z)(x,y,z) の総数は 6594497665944976 個です。

サンプル2
入力
4
出力
0

22 条件

{x3+y3+z3≡4(mod333)x4+y4+z4≤44444\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.

を全て満たす正整数の 33 つ組 (x,y,z)(x,y,z) は存在しません。何故ならば、333333 は 99 の倍数であるので 11 つ目の条件から x3+y3+z3≡4(mod9)x^3 +y^3 + z^3 \equiv 4 \pmod{9} であることが従いますが、立方数を 99 で割った余りは 0,1,80, 1, 8 の 33 通りしかなく、これらから重複を込めて 33 数をどう選んで足し合わせても法 99 で 44 に一致しないからです。

サンプル3
入力
10
出力
499924557

22 条件

{x3+y3+z3≡10(mod333)x4+y4+z4≤44444\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.

を全て満たす正整数の 33 つ組 (x,y,z)(x,y,z) の例には (2,1,1)(2,1,1) や (1,2,1)(1,2,1) や (1,1,2)(1,1,2) があります。そのような (x,y,z)(x,y,z) の総数は 499924557499924557 個です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。