剰余を求めるプログラム

初心者です。
aのb乗をcで割った時の余りを求めるプログラムを作りたいのですが、うまく作れません。
また、aのb乗はオーバーフローを起こしてしまう巨大な数です。
「一回一回積を計算してから剰余を求めていく」、や「long long int型を使う」などのヒントがありfor文を使って剰余を求めようとしましたがうまくできませんでした。
wikipediaで冪剰余について調べましたが関数を使わないでやってみるとのことなので関数を使わないで剰余を求めるプログラムを組むのはどうすればいいでしょうか？

No.2 ベストアンサー 回答者： asuncion 回答日時： 2007/11/26 23:20

例えばbが3のとき、

(a * a * a) % c == ((a * a) % c * a) % c
が成立します。bが4以上のときも、同じ考え方が成立します。
よって、aのb乗を直接求めずに、pow(a, b) % c を求めることができます。

この回答へのお礼

返事が遅れて申し訳ありません。
参考にさせて頂いたところ、なんとか完成しました。
ありがとうございました。
これからもがんばります。

お礼日時：2007/11/29 00:11

No.4 回答者： rabbit_cat 回答日時： 2007/11/27 04:13

フェルマーの小定理（またはオイラーの定理）を使うと、冪をあっというまに小さな数にできます。

http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7% …

この回答へのお礼

ありがとうございました。おかげ様で解決しました。
プログラミングだけでなく、数学の知識も増えた気がします。

お礼日時：2007/11/29 00:06

No.3 回答者： shred 回答日時： 2007/11/26 23:27

ヒントから、高速冪乗法を使う問題だと思われます。

参考URL：http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/ …

No.1 回答者： A-Tanaka 回答日時： 2007/11/26 23:10

浮動小数点の場合には、

#include <math.h>の中に、modfという関数があります。

しかしながら、整数型の場合には、関数（多分、再帰型関数）を作ってみないと無理かと思います。