1

n^n (1 ≤ n ≤ 10^9) の値を処理する最適化された方法

使用long long intしましたが、値が（1000 ^ 1000）になる可能性があるため、十分ではありません

GMP library http://gmplib.org/を検索して見つけましたが、BigInt classそれらを使用したくありません。これを処理するための数値的な方法を探しています。

の最初と最後のk (1 ≤ k ≤ 9) 桁を出力する必要がありますn^n

最初のk桁については、以下に示すように取得しています（これは少し醜い方法です）

num = pow(n,n);
while(num){
    arr[i++] = num%10;
    num /= 10;
    digit++;
}
while(digit > 0){
    j=digit;
    j--;
    if(count<k){
        printf("%lld",arr[j]);
        count++;
    }
    digit--;
}

最後のk桁はnum % 10^k以下のように使用しています。

findk=pow(10,k);
lastDigits = num % findk;
enter code here

k の最大値は 9 です。したがって、最大で 18 桁しか必要ありません。完全な n^n 式を実際に解かずに、これらの 18 桁を取得することを考えています。

任意のアイデア/提案??

4

3 に答える 3

5 
// note: Scope of use is limited.

#include <stdio.h>

long long powerMod(long long a, long long d, long long n){
// a ^ d mod n
    long long result = 1;
    while(d > 0){
        if(d & 1)
            result = result * a % n;
        a = (a * a) % n;
        d >>=1;
    }
    return result;
}

int main(void){
    long long result = powerMod(999, 999, 1000000000);//999^999 mod 10^9
    printf("%lld\n", result);//499998999

    return 0;
}
于 2013-05-21T08:38:02.837 に答える
0

bigintライブラリを使用したくないのはなぜですか?

bignum 演算を正しく効率的に行うのは非常に困難です。そのテーマに取り組むことで、博士号を取得することができます。

Fist、bigint 演算には自明でないアルゴリズムがあります

次に、bigint の実装には通常、単純な C では簡単にアクセスできない機械語命令 (キャリー付きの追加など) が必要です。

特定の問題（ N Nの最初と最後の数桁）については、複雑さを軽減するために（算術定理を使用して）紙の上で推論することをお勧めします。私は専門家ではありませんが、おそらくO(N)よりも複雑なため、依然として扱いにくいと思います。

于 2013-05-21T05:02:35.603 に答える