Biorąc pod uwagę dwie liczby ni am, oceń nieskończoną wieżę mocy:

n ^ (n + 1) ^ (n + 2) ^ (n + 3) ^ (n + 4) ^ ... mod m

Pamiętaj, że ^ ma właściwe skojarzenie. Więc 2 ^ 3 ^ 4 = 2 ^ (3 ^ 4). W jaki sposób możesz przypisać wartość nieskończonej sekwencji operatorów asocjacyjnych?

Zdefiniuj f (n, m, i) jako wieżę mocy zawierającą pierwsze terminy i nieskończonej wieży mocy. Następnie istnieje pewna stała C taka, że ​​dla każdego i> C, f (n, m, i) = f (n, m, C). Można więc powiedzieć, że nieskończona wieża mocy zbiega się na pewnej wartości. Interesuje nas ta wartość.

Twój program musi być w stanie obliczyć n = 2017, m = 10 ^ 10 w mniej niż 10 sekund na rozsądnym nowoczesnym komputerze. Oznacza to, że powinieneś wdrożyć rzeczywisty algorytm, bez brutalnego forsowania.

Możesz założyć, że n <2 ³⁰ i m <2 ⁵⁰ dla ograniczeń liczbowych w twoim języku programowania, ale twój algorytm musi teoretycznie działać dla dowolnego rozmiaru n , m . Jednak twój program musi być poprawny dla danych wejściowych w tych granicach wielkości, przepełnienia wartości pośrednich nie są usprawiedliwione, jeśli dane wejściowe mieszczą się w tych granicach.

Przykłady:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Pyth, 23 bajty

M&tG.^HsgBu-G/GH{PGGhHG

Określa funkcję g, z m i n , w tej kolejności.

Wypróbuj online

Jak to działa

M&tG.^HsgBu-G/GH{PGGhHG
M                         def g(G, H):
 &tG                        0 if G == 1, else …
                 PG         prime factors of G
                {           deduplicate that
          u-G/GH   G        reduce that on lambda G,H:G-G/H, starting at G
                              (this gives the Euler totient φ(G))
        gB          hH      bifurcate: two-element list [that, g(that, H + 1)]
       s                    sum
    .^H               G     H^that mod G

Python 2, 109 76 bajtów

import sympy
def g(n,m):j=sympy.totient(m);return m-1and pow(n,j+g(n+1,j),m)

Wypróbuj online!

Dlaczego to działa?

Używamy następującego uogólnienia twierdzenia Eulera .

Lemat. n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ) dla wszystkich n (niezależnie od tego, czy n jest coprime na m ).

Dowód: dla wszystkich głównych mocy p ^k dzielących m ,

• Jeśli p dzieli n , to dlatego, że φ ( m ) ≥ φ ( p ^k ) = p ^{k - 1} ( p - 1) ≥ 2 ^{k - 1} ≥ k , mamy n ^{2φ ( m )} ≡ 0 ≡ n ^{φ ( m )} (mod p ^k ).
• W przeciwnym razie, ponieważ φ ( p ^k ) dzieli φ ( m ), twierdzenie Eulera daje n ^{2φ ( m )} ≡ 1 ≡ n ^{φ ( m )} (mod p ^k ).

Dlatego n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ).

Następstwo. Jeśli k ≥ φ ( m ), to n ^k ≡ n ^{φ ( m ) + ( k mod φ ( m ))} (mod m ).

Dowód: jeśli k ≥ 2φ ( m ), lemat daje n ^k = n ^{2φ ( m )} n ^{k - 2φ ( m )} ≡ n ^{φ ( m )} n ^{k - 2φ ( m )} = n ^{k - φ ( m )} ( mod m ) i powtarzamy, aż wykładnik będzie mniejszy niż 2φ ( m ).

Haskell , 156 bajtów

(?)zajmuje dwa Integers i zwraca an Integer, użyj jako (10^10)?2017(odwrócona kolejność w porównaniu do OP.)

1?n=0
m?n=n&m$m#2+m#2?(n+1)
1#_=1
n#p|m<-until((<2).gcd p)(`div`p)n=m#(p+1)*1`max`div(n*p-n)(p*m)
(_&_)0=1
(x&m)y|(a,b)<-divMod y 2=mod(x^b*(mod(x*x)m&m)a)m

Wypróbuj online! (Tym razem testuję przypadki w nagłówku, ponieważ używają notacji potęgowania).

Co ciekawe, najwolniejszym przypadkiem testowym nie jest ten z ograniczeniem prędkości (to prawie natychmiast), ale ten 524287 ? 32, ponieważ 524287jest znacznie większą liczbą pierwszą niż wynika to z czynników innych przypadków testowych.

Jak to działa

• (x&m)yjest x^y `mod` mlub modem mocy, wykorzystując potęgowanie przez podniesienie do kwadratu.
• n#pjest funkcją całkowitą Eulera n, przy założeniu, że nnie ma mniejszych czynników pierwszych niż p.
  • mjest podzielony na nwszystkie pczynniki.
  • Jeśli istnieją ktakie czynniki, suma powinna sama otrzymać odpowiedni współczynnik (p-1)*p^(k-1), który jest obliczany jako div(n*p-n)(p*m).
  • 1`max`...obsługuje przypadek, w którym ntak naprawdę nie był podzielny, przez pco drugi argument jest maxrówny 0.
• Główna funkcja m?nwykorzystuje to, że gdy yjest wystarczająco duża, n^y `mod` mjest taka sama jak n^(t+(y`mod`t)) `mod` m, gdy tjest sumą m. (Jest t+to konieczne dla tych czynników głównych ni mmają one wspólne, które wszystkie zostają zmaksymalizowane).
• Algorytm zatrzymuje się, ponieważ iterowane funkcje totalizmu ostatecznie osiągają wartość 1.

Mathematica, 55 bajtów

n_~f~1=0;n_~f~m_:=PowerMod[n,(t=EulerPhi@m)+f[n+1,t],m]

Przykłady:

In[1]:= n_~f~1=0;n_~f~m_:=PowerMod[n,(t=EulerPhi@m)+f[n+1,t],m]

In[2]:= f[2, 10^15]

Out[2]= 566088170340352

In[3]:= f[4, 3^20]

Out[3]= 4

In[4]:= f[32, 524287]

Out[4]= 16

In[5]:= f[2017, 10^10]

Out[5]= 7395978241

Pari / GP , 59 bajtów

f(n,m)=if(m==1,0,lift(Mod(n,m)^((t=eulerphi(m))+f(n+1,t))))

Wypróbuj online!