調子に乗ってもう一問だけお願いいたします。
言語はｃです。
「正の整数ｎに対して、0<=i<=nなるiのうち、gcd(i,n)=1となるiの個数をψ(n)とする。適当な正の整数mに関して、1<=a<=mなるすべてのaについて、(aのψ(n)乗)*(modm)、gcd(a,m)を計算せよ。」
ヒントで、「ψ(n)、gcd(a,ｂ)、(aのk乗)*(modm)を計算する関数をそれぞれ定義するとよい。」
「aのk乗を計算する場合には、kの２進数展開を利用するとよい」
「(aのk乗)*(modm)を計算する際に、aのk乗を計算してから(modm)を計算しないこと」
とあります。よろしくお願いします。