プログラマ専用SNS ミクプラ

ｃ言語のプログラムで、「ｘの９５乗を３２３で割った余りを16進数に直す」というものを作りたいです

桁が大きすぎるのか、ｘ＝３７をいれると95乗が-1028680659で割ったものを-272という結果になり、マイナスがついてしまいます。
さらにx=250をいれると全て０になってしまいます。
１．この桁数の多さ？は解決する手段はないのでしょうか？
２．また、以下に表したプログラムでintからlongにする場合、全てのintをlongにするのですか？
わからないことが多くて困っています。ちなみに使ってるのはmicrosoft visualC++の2010です。
-----------------------------------------------------------
#include "stdafx.h"
#include <math.h>
#include <stdio.h>

int Power(int x, int y); //プロトタイプ宣言

int main(void)
{
int xi,yi,zi;

printf("整数を入力してください:");
scanf("%d",&xi);
yi=95;
zi=Power(xi,yi)%323;

printf("%dの%d乗は%dで、それを323で割った余りは%dです\n",xi,yi,Power(xi,yi),zi);
printf("十六進数表示は%xです",zi);

return 0;

}

int Power(int x, int y)
{
int i,result;
for( i=1, result = 1; i <= y; i++) {
result *= x;
}
return result;
}
---------------------------------------------------------------
結果

整数を入力してください：37
37の95乗は-102868059で、それを323で割ったあまりは-272です。
十六進数表示はfffffef0です

wai さんが書きました: １．この桁数の多さ？は解決する手段はないのでしょうか？

ヒント: (x ^ 95) % 323 = ((((((((x * x) % 323) * x) % 323) * x) % 323) * x) ... ) % 323
x ^ 95 という巨大な数を直接求める必要はありません

wai さんが書きました: ２．また、以下に表したプログラムでintからlongにする場合、全てのintをlongにするのですか？
わからないことが多くて困っています。ちなみに使ってるのはmicrosoft visualC++の2010です。

そうです。ただし、VisualC++では int も long int も32bitですのでどちらでも扱える整数の範囲は同じです。

まともに計算したらダメです、というか、
xが大きいと95乗を計算できないのは
今回の現象のとおりです。

「合同式」「剰余系」あたりについて研究してみてください。

wai さんが書きました:また、以下に表したプログラムでintからlongにする場合、全てのintをlongにするのですか？

違います。main関数の戻り値はlongではなくintを使うべきです。
また、もちろん「printf」に含まれる「int」もlongにしてはいけません。
テキストエディタの置換機能を使用するとよくあるミスなので、気をつけるべきです。

wai さんが書きました:この桁数の多さ？は解決する手段はないのでしょうか？

桁数は変わりませんが、GNU MPというライブラリを使用すれば、オーバーフローするという問題は解決できます。
ただし、ライブラリのライセンスがLesser General Public License version 3なので、公開時には注意が必要かもしれません。

h2so5 さんが書きました:ヒント: (x ^ 95) % 323 = ((((((((x * x) % 323) * x) % 323) * x) % 323) * x) ... ) % 323
x ^ 95 という巨大な数を直接求める必要はありません

さらにヒント : x=76543でテストしましょう。答えは10進数で121(16進数に直すと0x79)です。

考え方を少し変えてみると、うまくいくかもしれません。
例えば、x = 2の場合を考えてみます。

（1乗から7乗までは省略）
2^8 = 256を323で割ったあまりは、256です。
2^9 = 512を323で割ったあまりは、189です。
さて、次の2^10を323で割ったあまりを求める際、
2^10 = 1024をまともに計算するのではなく、
先に求めた189に2をかけた378を323で割ったあまりである55とするのです。
実際、2^10 = 1024を323で割ったあまりは55になりますね。
先ほどの回答で書いた合同式でいうと、
378 ≡ 1024 (mod 323)
378と1024は、323を法として合同である、と読みます。
378も1024も、323で割ったあまりは等しいという意味です。
1024を扱うよりは378を扱う方が、数値が小さくてすみますね。
べき乗の数値が大きくなっていくほど、10乗の場合における378と1024の違いが
さらに際立ってくるはずです。
xが大きくなれば、なおさらです。

今回のトピックの主題は最終的な値が桁溢れしない数なのでh2so5さんのやり方でいいと思います・・・・が！

wai さんが書きました:１．この桁数の多さ？は解決する手段はないのでしょうか？

とあり、例えば次に、「入力したｘの９５乗を求めて出力しろ」という課題が出たら詰むと思います。（調べればいい話なのですが・・・）
ですので調べたら「このようなページ」を見つけたので貼っておきます。（コメント欄まで読んだほうがいいかもです）

マルチポストだね。
http://detail.chiebukuro.yahoo.co.jp/qa ... 1121105256

zeek さんが書きました:マルチポストだね。
http://detail.chiebukuro.yahoo.co.jp/qa ... 1121105256

あっちで解答がついているので、もうこっちは見ないでしょう。

x の 95乗も求めないといけないのなら、多倍長計算ですね。
x < 10000 という制限付きですが。