回答編集履歴
4
冪乗ってO\(log n\)だったよね？
test
CHANGED
|
@@ -70,7 +70,7 @@
|
|
|
70
70
|
|
|
71
71
|
|
|
72
72
|
|
|
73
|
-
さて、これでもまだ不十分です。それぞれの冪乗計算が(n0 + 1) + (n1 + 1) + (n2 + 1) + ... + (pi + 1)個もあります。しかも、これらは個々にオーバーフローの可能性があるので、冪乗を計算してからmodをとることはできません。p^nをまともに計算したらO(n)になるので、間に合いません。そこで使うのはメモ化です。まずは、次の式が成り立つことに注目します。
|
|
73
|
+
さて、これでもまだ不十分です。それぞれの冪乗計算が(n0 + 1) + (n1 + 1) + (n2 + 1) + ... + (pi + 1)個もあります。しかも、これらは個々にオーバーフローの可能性があるので、冪乗を計算してからmodをとることはできません。p^nをまともに計算したらO(log n)になるので、間に合いません。そこで使うのはメモ化です。まずは、次の式が成り立つことに注目します。
|
|
74
74
|
|
|
75
75
|
|
|
76
76
|
|
3
続きを書いた
test
CHANGED
|
@@ -37,3 +37,51 @@
|
|
|
37
37
|
|
|
38
38
|
|
|
39
39
|
ですが、単純に一つ一つ計算した場合、たぶん、**間に合いません**。ではどうすするかなのですが、なんかCodeIQの問題っぽいので、12月01日（木）AM10:00の締め切りすぎてから、続きを書きます。
|
|
40
|
+
|
|
41
|
+
|
|
42
|
+
|
|
43
|
+
---
|
|
44
|
+
|
|
45
|
+
|
|
46
|
+
|
|
47
|
+
解説がすでにあるようですが、私は読んでません。間違っているかもです。
|
|
48
|
+
|
|
49
|
+
|
|
50
|
+
|
|
51
|
+
さて、「あとは各約数を一つ一つ計算して足すだけ」という話でしたが、それでは間に合わないだろうという話でした。ここからどうするかです。
|
|
52
|
+
|
|
53
|
+
|
|
54
|
+
|
|
55
|
+
まずは、計算量を減らすことを考えます。素因数分解された素数に対するそれぞれの数はn0, n1, n2, ... piとすると、約数だけで(n0 + 1) * (n1 + 1) * (n2 + 1) * ... * (pi + 1)個もあります。膨大な数です。これらを足して行くだけでもかなりの計算量です。しかも、それぞれの約数について計算しなければなりません。ということで、約数の総和について公式を用いて、計算数を減らすようにします。
|
|
56
|
+
|
|
57
|
+
|
|
58
|
+
|
|
59
|
+
p0^n0*p1^n2*p2^n2*... pi^ni
|
|
60
|
+
|
|
61
|
+
と素因数分解できるある数の約数の総和は
|
|
62
|
+
|
|
63
|
+
(p0^0 + p0^1 + .. + p0^n0) * (p1^0 + p1^1 + .. + p1^n1) * (p2^0 + p2^1 + .. + p2^n2) * ... * (pi^0 + pi^1 + .. + pi^ni)
|
|
64
|
+
|
|
65
|
+
で求められます。
|
|
66
|
+
|
|
67
|
+
|
|
68
|
+
|
|
69
|
+
それぞれはn回で、それが(i+1)個あるのでn0 + n1 + n2 + ... + ni + i回の計算で可能になります。掛け算から足し算ですので、かなり回数が減りました。
|
|
70
|
+
|
|
71
|
+
|
|
72
|
+
|
|
73
|
+
さて、これでもまだ不十分です。それぞれの冪乗計算が(n0 + 1) + (n1 + 1) + (n2 + 1) + ... + (pi + 1)個もあります。しかも、これらは個々にオーバーフローの可能性があるので、冪乗を計算してからmodをとることはできません。p^nをまともに計算したらO(n)になるので、間に合いません。そこで使うのはメモ化です。まずは、次の式が成り立つことに注目します。
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
|
|
77
|
+
p^n mod D = (p^(n-1) * p) mod D = (p^(n-1) mod D) * (p mod D) mod D
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
p^n mod Dを計算するときp^(n-1) mod Dがわかっていれば、p mod Dをかけて、mod Dするだけで済みます。nを0から順番に計算するのであれば、一つ前のp^(n-1) mod Dは計算済みのはずです。つまり、この計算済みの値を別途保存しておけば、次の値もすぐに求められると言うことです。この方法であれば、どんなにnが大きくなってもそれぞれはO(1)で計算できると言うことになります。この前に計算していた値を保存して使う方法をメモ化といいます。
|
|
82
|
+
|
|
83
|
+
|
|
84
|
+
|
|
85
|
+
こうして最終的な計算量はO(n0 + n1 + n2 + ... + ni)になり、たぶん、間に合うようになるでしょう。
|
|
86
|
+
|
|
87
|
+
|
2
続きは来月に！
test
CHANGED
|
@@ -25,3 +25,15 @@
|
|
|
25
25
|
|
|
26
26
|
|
|
27
27
|
余談ですが、割り算の場合は、剰余する数(法)が素数の場合のみ計算できるため、この系の問題が多い競技プログラミングでは法に10^9+7(素数)が使われる場合が多いです。
|
|
28
|
+
|
|
29
|
+
|
|
30
|
+
|
|
31
|
+
---
|
|
32
|
+
|
|
33
|
+
|
|
34
|
+
|
|
35
|
+
問題文ちゃんとみてなかった…。約数の総和でしたね。上は一番大きい約数、つまり、その数自身です。他の約数も同じように計算して足して剰余するだけです。
|
|
36
|
+
|
|
37
|
+
|
|
38
|
+
|
|
39
|
+
ですが、単純に一つ一つ計算した場合、たぶん、**間に合いません**。ではどうすするかなのですが、なんかCodeIQの問題っぽいので、12月01日（木）AM10:00の締め切りすぎてから、続きを書きます。
|
1
和じゃない、全部積だ。
test
CHANGED
|
@@ -8,19 +8,19 @@
|
|
|
8
8
|
|
|
9
9
|
```
|
|
10
10
|
|
|
11
|
-
(2^3
|
|
11
|
+
(2^3 * 3^3) % 1000000
|
|
12
12
|
|
|
13
|
-
= ((2^3) % 1000000
|
|
13
|
+
= ((2^3) % 1000000 * (3^3) % 1000000) % 1000000
|
|
14
14
|
|
|
15
|
-
= ((2 * 2 * 2) % 1000000
|
|
15
|
+
= ((2 * 2 * 2) % 1000000 * (3 * 3 * 3) % 1000000) % 1000000
|
|
16
16
|
|
|
17
|
-
= ((((2 % 1000000) * (2 % 1000000) * (2 % 1000000)) % 1000000
|
|
17
|
+
= ((((2 % 1000000) * (2 % 1000000) * (2 % 1000000)) % 1000000 * ((3 % 1000000) * (3 % 1000000) * (3 % 1000000)) % 1000000) % 1000000
|
|
18
18
|
|
|
19
19
|
```
|
|
20
20
|
|
|
21
21
|
|
|
22
22
|
|
|
23
|
-
実際計算するときは**オーバーフローしないように**、積や和を行う度に剰余を求める必要があります(上の式では積の後の剰余を省略していますが、計算する数によっては必要です)。また、1000000で割った値は2147483647(2^31-1)以下ですが、それらの積は2147483647を越える場合がありますので、64bit以上であることが保証された`long long`や`int_least64_t`を使うようにしてください。
|
|
23
|
+
実際計算するときは**オーバーフローしないように**、積や和を行う度に剰余を求める必要があります(上の式では一部の積の後の剰余を省略していますが、計算する数によっては必要です)。また、1000000で割った値は2147483647(2^31-1)以下ですが、それらの積は2147483647を越える場合がありますので、64bit以上であることが保証された`long long`や`int_least64_t`を使うようにしてください。
|
|
24
24
|
|
|
25
25
|
|
|
26
26
|
|