2

N と呼ばれる T 番号 (T は入力の最初の行) のリストが与えられ、それぞれの番号を出力しなければならないという特定の問題があり((2^N)-1)%(10^9+7)ます。次の制約が適用されます。

1 ≤ T ≤ 100
1 ≤ N ≤ 100000000

低い整数については正しい答えが得られますが、高い整数については正しくありません。pow()math.hの関数と関係があると思いますが、よくわかりません。

これが私のコードです：

#include <stdio.h>
#include <math.h>

int main(void) {
    unsigned int t, i;
    long long unsigned int ans, n, m = 1000000007;
    scanf("%u", &t);
    for (i = 0; i < t; ++i) {
        scanf("%llu", &n);
        ans = ((long long unsigned int)pow(2,n)-1)%m;
        printf("%llu\n", ans);
    }
    return 0;
}

したがって、基本的に、プログラムに次の入力を与えると:

6
1
2
3
4
5
100000000

出力が得られます：

1
3
7
15
31
582344007

出力の最初の 5 行は正しいですが、最後の行に 494499947 を取得したいと考えています。

正しい答えを与える wolfram alpha 出力については、こちらを参照してください。

私の質問が些細なことでしたら申し訳ありませんが、私はまだ C の詳細を学んでいます。

4

3 に答える 3

4

の結果はpow(2, 100000000)3000 万桁を超えます。整数型に変換できません ( もlong long unsigned int) - 大きすぎます!

ここで正確な結果を得るには、累乗剰余を使用する必要があります。

于 2013-11-10T22:04:00.443 に答える
0

あなたは pow を呼び出していますが、これには double が必要です。最大範囲が必要な場合は、少なくとも Linux で powl を使用します。これには長い倍の時間がかかります。あなたのプログラムには、オーバーフローや範囲エラーなどのチェックがありません。結果の正確さに関心がある場合は、これらを追加する必要があります。「man pow」をもっと詳しく読み直す必要があると思います:-)

于 2013-11-10T22:09:39.913 に答える