En primer lugar, tenga en cuenta que incluso si usted obtuvo un algoritmo de complejidad $O(r)$, esto sería todavía no ser eficiente, porque "rápida", significa $O(\log ^p r)$ para algunos entero $p$. $O(r)$ todavía medio tiempo exponencial, debido a que $r = 2^{\log r}$ que es exponencial en $\log r$. Como es habitual en ciencias de la computación, cuando escribo $\log$ me refiero a $\log _2$.
Segundo, el problema se complica por el hecho de que ninguno de $r$, $a$, $N$ es fija, es decir, todos ellos son libres para crecer, y usted probablemente desea que su algoritmo de ser rápido con respecto a todos los tres de ellos (no sólo de $r$). No es una tarea fácil.
Con el fin de diseñar un algoritmo para calcular su suma, intentemos primero se calcula el modulo algunos de los números primos $p$ (que vamos posteriormente decide ser "pequeño").
La realización de la división Euclídea, no existe $A, B$ tal que $N = Ap + B$$0 \le B < p$. Si $\hat a$ es el resto de $a$ modulo $p$ $\hat r$ el resto de $r$ modulo $p-1$ (sí, $p-1$, no $p$), luego su suma se convierte en
$$\sum \límites de _{i=1} ^p^i i^r + \sum \límites de _{i = p+1} ^{2} a^i i^r + \sum \límites de _{i = 2p+1} ^{3p} a^i i^r \dots + \sum \límites de _{i = (A-1)p+1} ^{Ap} a^i i^r + \sum \límites de _{i = Ap+1} ^{Ap+B} a^i i^r = \\
\sum \límites de _{i=1} ^p^i i^r + \sum \límites de _{i=1} ^p^{i+p} (i+p)^r + \sum \límites de _{i=1} ^p^{i+2p} (i+2p)^r + \dots + \sum \límites de _{i=1} ^p^{i+(A-1)p} (i+(A-1)p)^r + \sum \límites de _{i=1} ^B^{i+Ap} (i+Ap)^r \equiv \\
\sum \límites de _{i=1} ^{p-1} \hat^i i^ {\hat r} (1 + \hat ^p + \hat a ^{2} + \dots + \hat ^{(A-1)p}) + \hat ^{Ap} \sum \límites de _{i=1} ^B \hat ^i i^{\hat r} = \\
\frac {\hat ^{Ap} -1} {\hat^p -1} \sum \límites de _{i=1} ^{p-1} \hat ^i i^{\hat r} + \hat ^{Ap} \sum \límites de _{i=1} ^B \hat ^i i^{\hat r} .$$
Vamos a explicar una serie de cosas:
al final de la fórmula que abarca las líneas 2 y 3 hay una reducción modulo $p$
el límite superior de la suma ha cambiado de $p$ $p-1$porque las condiciones de con $i=p$ $0$ modulo $p$
lo anterior es válido si $\hat a ^p \ne 1 \mod p$ (que en realidad significa $\hat a \ne 1 (\mod p)$). Si $\hat a = 1 \mod p$, a continuación, reemplace la fracción por $A$
el salto de la $i^r$ $i^{\hat r}$es justificado por Fermat poco teorema: $x^{p-1} \equiv 1 (\mod p)$ siempre $x \ne 0 (\mod p)$ (y esta última condición es cumplida $i$ se detiene en $p-1$). Ya que por Euclidiana división no existe $q$ tal que $r = q(p-1) + \hat r$, $i^r = i^{q(p-1) + \hat r} = i^{\hat r}$
para las exponenciales uso exponenciación binaria realizando una reducción modulo $p$ en cada paso (o cualquier otra rápida exponenciación modular que usted se sienta cómodo).
La suma de dos en la última línea debe ser rápido para calcular debido a que todos los números involucrados $p, \hat a, \hat r, B$ son "pequeños" (es decir, menos de $p$ que, en sí mismo, es "pequeño").
La pregunta ahora es cómo construir el valor de su suma saberlo modulo varios "pequeños" de los números primos $p$. Vamos a utilizar el teorema del resto Chino, que voy a asumir que usted se familiarice con (si no, es ampliamente descrito en varios lugares en el internet). El hecho crucial aquí es que el resultado se supone que se calcula el modulo $10^9 + 7$.
Encontrar $d$ números primos $p_1 \le \dots \le p_d$ tal que $p_1 p_2 \dots p_d \ge 10^9 + 7$. Cómo de grande debe $d$? Así, imponer la condición de $p_1 ^d \ge 10^9 + 7$, y si usted toma $p_1 = 2$ usted puede optar $d = \lfloor \log (10^9 + 7) \rfloor +1 = 30$. Puesto que el $30$-ésimo número primo es $113$, esto equivale a la elección de $p_1 = 2, p_2 = 3, p_3 = 5, \dots, p_{30} = 113$. Por supuesto, usted puede elegir un conjunto diferente de números primos, haciéndolos menos pero más grandes. El tiempo tomado por un programa concreto probablemente variará, pero no su complejidad clase.
Para cada una de las $1 \le j \le 30$, hacer su cálculo modulo $p_j$ como se describió anteriormente. Por último, aplica el teorema del resto Chino a la $d=30$ resultados así obtenidos. Esto producirá un (único) resultado entre el$0$$p_1 p_2 p_3 \dots p_{30}$. Finalmente, el resto de este resultado modulo $10^9 + 7$. Esta es la respuesta al problema.
Algunos comentarios finales: como se puede ver, que no requieren la solución modulo algún número ($10^9 + 7$, que pasa a ser el primer pero esto no nos ayuda), que habría hecho que el problema intratable para números grandes. La idea anterior fue para descomponer el problema en muchos problemas similares de pequeño tamaño, resolver cada uno de estos y combinar sus resultados. Esta es una idea general de programación, y el enfoque de arriba se utiliza a menudo cuando se trabaja con grandes cálculos de enteros. Mantenga en mente para futuros problemas.
PS: Se que hacer trampa y mirando aquí en busca de respuestas a problemas de Project Euler?
