prithivMLmods/Coder-Stat

1 2 3 4<h1>素数の性質</h1>5 6<p>74 で割ると 3 あまる素数 <var>n</var> (11、19、23 など) には、面白い性質があります。1 以上 <var>n</var> 未満の自然数 (1, 2,... , <var>n</var> - 1) を 2 乗したものを <var>n</var> で割ったあまりを計算した結果を並べると、同じ数になるものがあるため、互いに異なった数の個数は、(<var>n</var> - 1)/2 になります。8</p>9 10<p>11この様にして得られた数の集合には、特別な性質があります。得られた数の集合から、互いに異なる 2 つ <var>a</var> と <var>b</var> を選んでその差を計算します。差が負になったときは、その差に <var>n</var> を足します。さらに結果が (<var>n</var> - 1)/2 より大きいときは、その差を <var>n</var> から引きます。12</p>13 14<p>15例えば、<var>n = 11</var> のとき 1 と 9 の差は、<var>1 &minus; 9 = &minus;8</var>  → <var>&minus;8 + n = &minus;8 + 11 = 3</var> になります。9 と 1 の差も <var>9 &minus;1 = 8</var> → <var>n &minus; 8 = 11 &minus; 8 = 3</var> で、同じ値 3 になります。この差は、円周上に 0, 1, ・・・, <var>n</var> - 1 を書いて、二つの数字の間の短い方の円弧を考えるとわかりやすくなります。(下図参照)16</p>17<center>18<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_natureOfPrimeNumber1">19</center>20<br/>21 22<p>23  こうして得られた数の「差」は、1, 2, . . ., (<var>n</var> - 1)/2 のいずれかであり、同じ回数出現します。24</p>25 26<p>27【例】 <var>n = 11</var> の時は、以下のようになります。28</p>29 30<ol>31<li> 1 から <var>n</var>-1 までの数を 2 乗したものを <var>n</var> で割った余りを計算します。32<pre>33 1<sup>2</sup>  =    1   →   134 2<sup>2</sup>  =    4   →   435 3<sup>2</sup>  =    9   →   936 4<sup>2</sup>  =   16   →   537 5<sup>2</sup>  =   25   →   338 6<sup>2</sup>  =   36   →   339 7<sup>2</sup>  =   49   →   540 8<sup>2</sup>  =   64   →   941 9<sup>2</sup>  =   81   →   44210<sup>2</sup>  =  100   →   143</pre>44</li>45 46 47<li> <var>a</var>, <var>b</var> の「差」の計算<br><br>48       <ol>49<li> 1 で得られた 1, 3, 4, 5, 9 について異なる数同士の差を計算します。</li>50<li> 計算結果が負の場合、<var>n</var> = 11 を加算します。</li>51<li> さらに、計算結果が  (<var>n</var>-1)/2 = 5 より大きい場合 <var>n</var> = 11 から減算します。</li>52       </ol>53</li>54 55<li>出現回数を求める<br>56<p>57計算結果 1, 2, 3, 4, 5 の出現回数をそれぞれ数え上げます。58</p>59</li>60</ol>61 62 63<p>64これらの計算結果から 1, 2, 3, 4, 5 の出現回数が 4 回であることがわかります。この性質は 4 で割ると 3 あまる素数特有の性質であり 4 で割ると 1 あまる素数ではこのようなことはおきません。このことを確認するため、10000 以下の奇数 <var>n</var> を入力とし、例題にあるような計算 (<var>n</var> で割ったあまりの 2 乗の差の頻度を求める)を実行し、その出現回数を出力するプログラムを作成してください。65</p>66 67<!--68<td><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE_natureOfPrimeNumber2"></td>69-->70 71<H2>Input</H2>72 73<p>74複数のデータセットが与えられます。各データセットとして１つの整数 <var>n</var>　(<var>n</var> &le; 10000) が１行に与えられます。入力は 0 を１つ含む行でおわります。75</p>76 77<H2>Output</H2>78 79<p>80各データセットについて、出現頻度を以下の形式で出力してください。81</p>82 83<pre>84剰余の平方の差が 1 である(<var>a, b</var>)の出現個数(整数)85剰余の平方の差が 2 である(<var>a, b</var>)の出現個数(整数)86   :87   :88剰余の平方の差が (<var>n</var>-1)/2 である(<var>a, b</var>)の出現個数(整数)89</pre>90 91<H2>Sample Input</H2>92 93<pre>9411951596097</pre>98 99<H2>Output for the Sample Input</H2>100 101<pre>102410341044105410641072108210941102111411241132114</pre>115 116 117 118