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

[wai]

ｃ言語のプログラムで、「ｘの９５乗を３２３で割った余りを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です

[h2so5]

１．この桁数の多さ？は解決する手段はないのでしょうか？

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

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

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

[box]

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

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

[みけCAT]

また、以下に表したプログラムでintからlongにする場合、全てのintをlongにするのですか？

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

[みけCAT]

この桁数の多さ？は解決する手段はないのでしょうか？

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

[みけCAT]

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

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

[box]

考え方を少し変えてみると、うまくいくかもしれません。
例えば、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が大きくなれば、なおさらです。

[sql]

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

１．この桁数の多さ？は解決する手段はないのでしょうか？

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

[zeek]

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

[かずま]

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

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

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

コード:

#include <stdio.h>
 
#define B 10000  // 万進法 (Base = 100)
#define N 100    // 万進100桁, 十進400桁

int mul(int *a, int b)  // a *= b, return carry
{
    int i, t, c = 0;
    for (i = 0; i < N; i++) t = a[i] * b + c, c = t / B, a[i] = t % B;
    return c;
}

int mod(const int *a, int b) // return a % b 
{
    int i = N, r = 0;
    while (--i >= 0) r = (a[i] + r * B) % b;
    return r;
}

void print(const int *a) 
{
    int i= N;
    while (--i > 0 && a[i] == 0) ;
    printf("%d", a[i]);
    while (--i >= 0) printf("%04d", a[i]);
}

int main(void)
{
    int i, x, r, a[N] = { 1 };
    printf("整数を入力してください: "); 
    if (scanf("%d", &x) != 1 || x < 0 || x >= B) return 1;
    for (i = 0; i < 95; i++) if (mul(a, x)) return 1;
    r = mod(a, 323);
    printf("%d の 95乗は ", x); 
    print(a);
    printf(" で、\nそれを 323で割った余りは %d です\n16進数表示は %x です\n", r, r); 
    return 0;
}