G - 魔方陣 Editorial

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は魔方陣が大好きです。

魔方陣というのは33マス×33マスの方陣に相異なる正の整数を配置して、タテ・ヨコ・ナナメいずれの列についても、その列の 33 つの整数の和が等しくなっているようなものの事です。

高橋君はふと、 33 つの和が等しいのではなく 33 つの積が等しいような「積バージョンの魔方陣」が作れるのではないかと思いました。

がんばって模索したところ、下図のような積バージョンの魔方陣を1つ作ることが出来ました。

ナナメも含めたすべての列の積が 10001000 になっています。

高橋君は今度は中央のマスが NN であるような積バージョンの魔方陣は何種類あるのか気になりました。

ここで 9090 度回転や左右反転などによって変換できる 22 つの魔方陣は区別しないとします。

高橋君のために、中央のマスが NN であるような積バージョンの魔方陣の種類を求めてください。


入力

入力は以下の形式で標準入力から与えられる

NN
  • 11 行目には積バージョンの魔方陣の中央の値 N(1N1012)N (1 ≦ N ≦ 10^{12}) が与えられる。

出力

中央のマスが NN であるような積バージョンの魔方陣の種類を 11 行で出力せよ。 出力の末尾には改行をいれること。


入力例1Copy

Copy
16

出力例1Copy

Copy
1

以下の様なパターンは配置されている整数が重複しているので魔方陣ではありません。

以下の様なパターンは全て回転や反転によって同じものに変換することができます。


入力例2Copy

Copy
10

出力例2Copy

Copy
1

入力例3Copy

Copy
9

出力例3Copy

Copy
0

入力例4Copy

Copy
90

出力例4Copy

Copy
29


2025-01-01 (Wed)
06:52:30 +00:00