DouKaku?

出題者です.

条件を緩めることにしました. 以下の2条件のうちお好きな方を選んでください.

条件(易)

1. 組み込み及びライブラリにあるgcdは使用禁止
2. 除算および剰余の使用禁止
3. 加算や乗算から除算・剰余を単純に定義することも禁止とする
4. ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
5. 引数は1-10000の間の二つの整数として構わない

条件(難)

1. 組み込み及びライブラリにあるgcdは使用禁止
2. 除算および剰余の使用禁止
3. 加算や乗算から除算・剰余を単純に定義することも禁止とする
4. ただし, ビットシフトが面倒な場合には引数を2で割った商を返す関数を実装しても構わない
5. 引数は二つの正整数として構わない (多倍長演算もあるとなお良い)

補足

• (fib 2000) => 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125
• (fib 1999) => 2611005926183501768338670946829097324475555189114843467397273230483773870037923307730410719313972291638157639230613843870597997481070930648667960025707364078851859017098672504986584144842548768373271309551281830431960537091677315014266625027123872238011234749984205478230617988978500613170516952885123444971471854671812569739975450866912490650853945622130138277040986146312325044424769652148982077548213909414076005501