No.2187 Sum of Three Cubes mod 333
タグ : / 解いたユーザー数 46
作問者 : 👑
testestest
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もしくは右上の雲マークをクリックしてアカウントを作成してください。