No.152 The Disappearance of the Piggy Bank
タグ : / 解いたユーザー数 177
作問者 :
なお
Problem Statement
Taro has a piggy bank that he treasures very much.
It was a present he received on his $N$-th birthday.
One day, however, the piggy bank he had carefully put away suddenly disappeared.
So Taro decided to search for it using his specialty, black magic. When he opened his book of black magic, he found the following:
"Draw a magic circle as shown in the figure below with string, and stand a candle in the center.
All the right triangles must be the same size, and all side lengths must be positive integers."
That is what was written.
Taro now has a string of length $L$.
Assuming he can freely cut and bend this string,
find the number of kinds of shapes of magic circles that Taro can make.
Here, a magic circle that is simply an integer multiple of another magic circle,
as well as rotated or flipped shapes, are considered to be the same shape.
Afterward, right after he safely found where the piggy bank was, Taro apparently stormed into Jiro's room.
Input
L
An integer $L\ (1 \leq L \leq 10,000,000 = 10^7)$ representing the length of the string is given.
Output
Output the number of kinds of shapes of magic circles that Taro can make, modulo $1000003$.
Print a newline at the end.
Sample
Sample 1
Input
165
Output
3
$3$ magic circles can be made, using right triangles with side lengths $(3,4,5)$, $(5,12,13)$, and $(8,15,17)$.
The string lengths required for them are $48$, $120$, and $160$ respectively, which fit within the length $165$.
Sample 2
Input
8765
Output
152
Sample 3
Input
47
Output
0
The string is too short, so no magic circle can be made.
The whereabouts of the piggy bank have become unknown.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。