8

上記のシリーズの合計を見つけるために、大きなn（たとえば10 ^ 10）の効率的なアルゴリズムのアイデアを教えてもらえますか？

Mycode は n= 100000 および m=200000 で殺されています

#include<stdio.h>

int main() {
    int n,m,i,j,sum,t;
    scanf("%d%d",&n,&m);
    sum=0;
    for(i=1;i<=n;i++) {
        t=1;
        for(j=1;j<=i;j++)
            t=((long long)t*i)%m;
        sum=(sum+t)%m;
    }
    printf("%d\n",sum);

}
4

6 に答える 6

24

2つのメモ：

(a + b + c) % m

と同等です

(a % m + b % m + c % m) % m

と

(a * b * c) % m

と同等です

((a % m) * (b % m) * (c % m)) % m

その結果、O（log p）の再帰関数を使用して各項を計算できます。

int expmod(int n, int p, int m) {
   if (p == 0) return 1;
   int nm = n % m;
   long long r = expmod(nm, p / 2, m);
   r = (r * r) % m;
   if (p % 2 == 0) return r;
   return (r * nm) % m;
}

forそして、ループを使用して要素を合計します。

long long r = 0;
for (int i = 1; i <= n; ++i)
    r = (r + expmod(i, i, m)) % m;

このアルゴリズムはO（n log n）です。

于 2009-10-01T09:59:02.307 に答える
5

ファイ（200000）= 80000のように、オイラーの定理を使用して累乗を回避できると思います。中国の剰余定理もモジュロを減らすので役立つかもしれません。

于 2009-10-01T10:21:18.840 に答える
3

この投稿に対する私の回答をご覧ください。そこの実装は少しバグがありますが、アイデアはそこにあります。重要な戦略は、n^(x-1)<m かつ n^x>m となるような x を見つけ、繰り返し n^n%m を (n^x%m)^(n/x)*n^( n%x)%m。この戦略はうまくいくと確信しています。

于 2009-10-01T10:09:34.777 に答える
1

最近、同様の質問に遭遇しました: 私の「n」は 1435、「m」は 10^10 です。これが私の解決策です（C＃）：

ulong n = 1435, s = 0, mod = 0;
mod = ulong.Parse(Math.Pow(10, 10).ToString());
for (ulong i = 1; i <= n; 
{
     ulong summand = i;
     for (ulong j = 2; j <= i; j++)
     {
         summand *= i;
         summand = summand % mod;
     }
     s += summand;
     s = s % mod;
}

末尾の 's' は必要な数に等しくなります。

于 2012-10-11T06:26:20.430 に答える
0

コメントを追加することはできませんが、中国の剰余定理については、http://mathworld.wolfram.com/ChineseRemainderTheorem.html式 (4)-(6) を参照してください。

于 2009-10-01T18:29:18.997 に答える
0

あなたはここで殺されていますか：

for(j=1;j<=i;j++)
    t=((long long)t*i)%m;

指数 mod m は、平方和法を使用して実装できます。

n = 10000;
m = 20000;
sqr = n;
bit = n;
sum = 0;

while(bit > 0)
{
    if(bit % 2 == 1)
    {
        sum += sqr;
    }
    sqr = (sqr * sqr) % m;
    bit >>= 2;
}
于 2009-10-01T12:57:48.107 に答える