剰余を求めるプログラム

質問

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

回答No.2

asuncion · ベストアンサー

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

お礼

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

回答No.4

rabbit_cat

フェルマーの小定理（またはオイラーの定理）を使うと、冪をあっというまに小さな数にできます。
http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%AB%E3%83%9E%E3%83%BC%E3%81%AE%E5%B0%8F%E5%AE%9A%E7%90%86

お礼

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

回答No.3

shred

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

参考URL：

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/power.html

回答No.1

A-Tanaka

浮動小数点の場合には、
#include <math.h>の中に、modfという関数があります。

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