• ベストアンサー

剰余を求めるプログラム

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

質問者が選んだベストアンサー

  • ベストアンサー
  • asuncion
  • ベストアンサー率33% (2127/6289)
回答No.2

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

fashle
質問者

お礼

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

その他の回答 (3)

  • rabbit_cat
  • ベストアンサー率40% (829/2062)
回答No.4

フェルマーの小定理(またはオイラーの定理)を使うと、冪をあっというまに小さな数にできます。 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

fashle
質問者

お礼

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

  • shred
  • ベストアンサー率35% (25/70)
回答No.3

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

参考URL:
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/power.html
  • A-Tanaka
  • ベストアンサー率44% (88/196)
回答No.1

浮動小数点の場合には、 #include <math.h>の中に、modfという関数があります。 しかしながら、整数型の場合には、関数(多分、再帰型関数)を作ってみないと無理かと思います。

関連するQ&A

専門家に質問してみよう