#この記事、何?
某有名QAサイトでたまたま見かけたをみて、面白そうだから計算してみた。
「37の95乗を323で除算したあまりを計算する」という話。
やっていたらいろいろ思っていた以上に面白かった。
具体的にはVisual Studio抜きでC#を計算するfor文作って計算したという話。
最後はちょっとだけ整数に関する話。

※追記※
皆さんコメントありがと~です。
いったん追記した時に評価を保留した式と、その後にもらったコメントについて、
別記事書くことにしました。
深堀してみたらそれぞれ面白いかったので。

#発端
少し前にPythonで1000乗とか計算してて、「for文書いて1000回回しちゃダメ!」って書いてあった。
要するに、|log2(n)|回くらいの計算で行けるでしょ、という話。
だったらこれも7回ループすれば行けるよね、とおもっって、作ってみた。

#方針
95って、2進数だと1011111。
リトルエンディアンとして下のビットから数える。
1回目、2回目、3回目、4回目、5回目、7回目にそれまでに用意した数で得処理して、扱えば行ける・・・かな?
やってみよう、と。

#コンパイル
Visual Studioなしでコンパイルできるよ。
方法は例によってこれ参照で。

■C#手遊び(Compiler w/o Visual Studio)
https://qiita.com/siinai/items/8a325ad4eade1a2f6e9e

#できあがり
書いてみたらあっさりいったのでソース全文を。
リアルに「処理」している本文は10行程度。。。

using System;
using System.Collections.Generic;

public class calc
{
    public static void Main(string[] args)
    {
        //x = 37, y = 95, z = 323  -> 227
        if (args.Length != 3) { return; }

        int x, y, z;
        int tmp = 1;
        var XX = new List<int>();
        int.TryParse(args[0], out x);
        int.TryParse(args[1], out y);
        int.TryParse(args[2], out z);
        Console.WriteLine("x = [" + x.ToString() + "]");
        Console.WriteLine("y = [" + y.ToString() + "]");
        Console.WriteLine("z = [" + z.ToString() + "]");

        Func<int, int, int> f = (a, b) => (int)Math.Pow(a, b);

        XX.Add(x);

        for (int itr = 0; itr < 100; itr++)
        {
            if (y % f(2, itr + 1) != 0)
            {
                tmp = (tmp * f(XX[itr], 1)) % z;
                y -= f(2, itr);
            }
            //無駄なループをなくすためにExit
            if (y == 0) { break; }
            //ループを実況。。。
            Console.WriteLine("itr = [" + itr.ToString() + "], y = [" + y.ToString() + "]");
            XX.Add(f(XX[itr], 2) % z);
        }
        
        Console.WriteLine(tmp.ToString());

    }
}

#ラムダ式
全部整数で処理したかったのでSystem.Math.Pow()を使用した。
ただ、戻り値型がdoubleでcastが必要で、何度も何度も出てくるので、いちいちcastするのがめんどくなった。
というわけでラムダ式。ちょっと前から書き始めてみたけど、慣れると面白い。
こういう手遊びでちょこちょこ入れていくと、自分の中にしみこんできている気がするわ。

#最後に検算方法
検算にはPythonを使った。

冒頭にC#で実質10行でできた、みたいなことを書いたけど、Pythonすごい。

>>> 37**95%323
227

10行どころか、10文字。身もふたもない。。。

おかげで検算は助かる助かる。

■C#の出力

C:\projects\qiita\draft\27>27-01.exe 37 95 323
x = [37]
y = [95]
z = [323]
227

C:\projects\qiita\draft\27>27-01.exe 3333 3333 12345
x = [3333]
y = [3333]
z = [12345]
5613

C:\projects\qiita\draft\27>27-01.exe 9343 13953 38424
x = [9343]
y = [13953]
z = [38424]
1999

■Pythonの出力

>>> 37**95%323
227
>>> 3333**3333%12345
5613
>>> 9343**13953%38424
1999
>>>

#蛇足
最後の検算、9343を何乗かして38424で割るパターン。
入力ミスで、13953乗ではなく、133953乗で計算してた。でも答えがあってた。
ちょっと計算してみたら、800乗単位であまりが1でループするみたい。

>>> for i in range(1000):
...     tmp = 9343**i%38424
...     if tmp < 500:
...         print(str(i) + ':' + str(tmp))
...
0:1
31:199
68:25
70:145
399:487
528:337
544:361
604:385
653:103
657:391
730:265
800:1
831:199
868:25
870:145
>>>

・・・なるほど。確かに最初、書きかけのコードが5ループ目で間違って抜けてしまっていて、37^95ではなく、37^15を計算してたけど、答えはあってたんだよね・・・
出題としてはどうだろうと思ったけど、除余を求めるという性質からすると仕方のないこと、かしら?


>>> 37**95%323
227
>>> 37**15%323
227
>>>

#感想
ちょっとだけC#やPython書きなれたよね、ということ込みでおもしろかった。
次はlambdaとかクラス継承とかのキャッチ-(?)な話題書きたいな。

#追記：コメントありがとうございます！

2種類コメントもらったのでそれぞれを追記します。

##その１：7回といいつつ100回ループしてるよ！

・・・はい。そうですね。
端折ったというか、深く考えてなかったというか・・・
3333^3333 を12345で割った余りを一瞬で返してくれるのでそこまでよくしようと思ってませんでした。
elseでbreak書く感じですよね。
書き足しました。
実行結果はこんな感じ。

C:\projects\qiita\draft\27>27-01.exe 37 95 323
x = [37]
y = [95]
z = [323]
itr = [0], y = [94]
itr = [1], y = [92]
itr = [2], y = [88]
itr = [3], y = [80]
itr = [4], y = [64]
itr = [5], y = [64]
227

7回?6回?うーん・・・まあ、いいか。

よく考えたら、itrの制限が32bit数値の制限にかかるから30くらいでよかったね・・・

##その２:でっかい数って、処理できてないんじゃない？

###C#側
そこは大丈夫だと思う。
各イテレーションでもらった数と、ストックしている数とかけて、それを割った余りを保持して処理しているから。
こんな。

[1回目]
3737 % 323 = 1369 % 323 = 77
[2回目]
7777 % 323 = 5929 % 323 = 115
[3回目]
115*115 % 323 = 13225 % 323 = 305
...

なので現れる数は上の例だと 322^2 以下の数しか現れないかな、と。
ホントは、最初の変数保持で、32bit変数の上限のルート(2^7.5くらい?)とかを判断して制限しようかと思ったけど、主目的以外のコードが増えて本題が薄くなるので見送ってしまいました。
(わかりづらかったですね。すみません。)

###Python側(検算用)
こっちも大丈夫だと思う。
前に、こんなの書いた。
その時、20!を計算して19桁の数だって言ってた。
その時どこまで行くのかと思って数増やしてみたら998!まで計算して999!でエラーになった。
再帰ロジックのiterationの数の制限らしく、どこかにここ変えたら外せるよって書いてあったけど・・・そこまでは試してない。
それとは別に、(998!)^2とか、(998!)^5とか・・・
結局普通に(998!)^100を計算させたら何画面分もの大量の数字を出してた。
すごいね。ここまできたら普通にグラハム数を計算できるんじゃないって気がしてきた。(いや、さすがに嘘ですが)

念のため、改めて100!を計算してみた。
末尾に0が24個あるから正しく計算している必要条件を満たすのであってるかな・・・と。
(1~100に5の倍数が20個、25の倍数が4個あるのでプラス4個で24個0が並ぶはず。)

■C#手遊び(フォームメニューを再帰ロジックで作る)
https://qiita.com/siinai/items/d2801021d28f77692cbc

#階上計算 / e.g.: fact(6) = 6! = 1*2*3*4*5*6 = 720
def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n-1)

#実行結果
>>> fact(20)
2432902008176640000
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>>>

とはいえお二人ともコメントありがとうございます。
あとで、

Enumerable.Repeat(37, 95).Aggregate(1, (a, b) => a * b % 323)

を試してみます！
(正直、出てくるキーワード、全部知らない。。。)