問題一覧 > 教育的問題

No.2187 Sum of Three Cubes mod 333

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 0.100秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 46
作問者 : 👑 p-adic / テスター : testestest
お気に入りにしたユーザー ProblemId : 8805 / 自分の提出
問題文最終更新日: 2023-01-13 21:47:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 373 (順位表) の他の問題:

Note

The execution time limit for this problem is 100ms.

Problem Statement

A positive integer $A$ is given as input.

 

Find the total number of $3$-tuples $(x,y,z)$ of positive integers that satisfy all of the following $2$ conditions:

$\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. $

Input

The input is given from standard input in the following format:

$A$

Constraints

The input satisfies the following constraints:

  • $A$ is a positive integer not greater than $333$

Output

Print on $1$ line the total number of $3$-tuples $(x,y,z)$ of positive integers that satisfy all of the following $2$ conditions:

$\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. $

It is known that the number of such $(x,y,z)$ is finite.

Print a newline at the end.

Sample

Sample 1
Input
3
Output
65944976

An example of a $3$-tuple $(x,y,z)$ of positive integers that satisfies all of the following $2$ conditions

$\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. $

is $(1,1,1)$. The total number of such $(x,y,z)$ is $65944976$.

Sample 2
Input
4
Output
0

There is no $3$-tuple $(x,y,z)$ of positive integers that satisfies all of the following $2$ conditions:

$\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. $

This is because, since $333$ is a multiple of $9$, the $1$st condition implies $x^3 +y^3 + z^3 \equiv 4 \pmod{9}$; however, the remainder of a cube when divided by $9$ can only be one of the $3$ values $0, 1, 8$, and no matter how $3$ numbers are chosen from these, with repetition allowed, and added together, their sum is not congruent to $4$ modulo $9$.

Sample 3
Input
10
Output
499924557

Examples of $3$-tuples $(x,y,z)$ of positive integers that satisfy all of the following $2$ conditions

$\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. $

include $(2,1,1)$, $(1,2,1)$, and $(1,1,2)$. The total number of such $(x,y,z)$ is $499924557$.

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