2

次のシーケンスの値を評価するためにコーディングする必要があります。

( pow(1,k) + pow(2,k) + ... + pow(n,k) ) % MOD n、k、およびMODの特定の値に対して。

インターネットで検索してみました。方程式を得ましたここに画像の説明を入力。ゼータ関数が含まれており、実装が難しいようです。同じことを実装するための簡単なアプローチが必要です。n の値が大きいため、単純に力ずくで制限時間を超えることはできません。

4

3 に答える 3

1

パイソンを使うだけ

k=input("Enter value for K: ")
n=input("Enter value for N: ")
mod=input("Enter value for MOD: ")
sum=0
for i in range(1,n+1):
    sum+=pow(i,k)
result=sum % mod
print mod

このコードが役立つかもしれません。

于 2014-08-18T13:03:00.287 に答える
1

ニュートンのアイデンティティーが役立つかもしれません。1..n を根とする多項式の係数を計算します。それはかなり些細なことです。次に、ID を使用します。

力の和を見たときに最初に頭に浮かぶのはそれだ。

モジュラー算術とうまく互換性があると思います-乗算と加算のみがあります。

ニュートンの恒等式は用語の再配置にすぎないことを認めなければならないので、ここではあまり速度が向上しません。

于 2012-06-30T10:06:17.653 に答える
0

math.stackexchange.com の方が良いことに同意します。

しかし、パラメータによっては、問題をより扱いやすくするランダムな事実があります。

まず、 を因数MOD分解し、素数の力率ごとに解いてから、中国剰余定理を使用して の答えを見つけますMOD。したがって、一般性を失うことなく、MOD は素数であると見なすことができます。

1^k + ... + MOD^k次に、は常に で割り切れることに注意してくださいMOD。nしたがって、 で置き換えることができますn mod MOD。

次に、 と が で割り切れない場合MOD = p^i、jはpmodj^((p-1) * p^(i-1))で1あるMODため、 のサイズを小さくすることができkます。

もちろん、(k, n) < MODandMODが素数の場合、これはまったく役に立ちません。(この問題がどのように発生するかによっては、これが当てはまる可能性があります。)

(kが十分に小さい場合、合計を生成できる明示的な式があります。しかし、 for は、kそのアプローチを扱いにくくするのに十分な大きさになる可能性があるようです。)

于 2012-06-30T17:27:48.887 に答える