Diberi dua angka n dan m, evaluasi menara listrik tanpa batas:

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

Perlu diingat bahwa ^ asosiatif-benar. Jadi 2 ^ 3 ^ 4 = 2 ^ (3 ^ 4). Sekarang bagaimana Anda bisa menetapkan nilai ke urutan tak terbatas operator asosiasi kanan?

Tentukan f (n, m, i) sebagai menara listrik yang berisi syarat-syarat i pertama dari menara listrik tanpa batas. Lalu ada beberapa konstanta C sehingga untuk setiap i> C, f (n, m, i) = f (n, m, C). Jadi Anda bisa mengatakan menara listrik tak terbatas berkumpul pada nilai tertentu. Kami tertarik dengan nilai itu.

Program Anda harus dapat menghitung n = 2017, m = 10 ^ 10 dalam waktu kurang dari 10 detik pada PC modern yang wajar. Artinya, Anda harus menerapkan algoritma yang sebenarnya, tanpa bruteforcing.

Anda dapat mengasumsikan bahwa n <2 ³⁰ dan m <2 ⁵⁰ untuk batas numerik dalam bahasa pemrograman Anda, tetapi algoritma Anda harus secara teoritis bekerja untuk ukuran apa pun n , m . Namun program Anda harus benar untuk input dalam batas ukuran ini, kelebihan nilai menengah tidak dimaafkan jika input berada dalam batas ini.

Contoh:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Pyth, 23 byte

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

Menentukan fungsi g, mengambil m dan n dalam urutan itu.

Cobalah online

Bagaimana itu bekerja

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 byte

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

Cobalah online!

Mengapa ini berhasil?

Kami menggunakan generalisasi teorema Euler berikut ini .

Kata pengantar singkat. n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ) untuk semua n (apakah n adalah coprime atau tidak terhadap m ).

Bukti: Untuk semua kekuatan utama p ^k membagi m ,

• Jika p membagi n , maka karena φ ( m ) ≥ φ ( p ^k ) = p ^{k - 1} ( p - 1) ≥ 2 ^{k - 1} ≥ k , kita memiliki n ^{2φ ( m )} ≡ 0 ≡ n ^{φ ( m )} (mod p ^k ).
• Jika tidak, karena φ ( p ^k ) membagi φ ( m ), teorema Euler memberikan n ^{2φ ( m )} ≡ 1 ≡ n ^{φ ( m )} (mod p ^k ).

Oleh karena itu, n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ).

Akibat wajar. Jika k ≥ φ ( m ), maka n ^k ≡ n ^{φ ( m ) + ( k mod φ ( m ))} (mod m ).

Bukti: Jika k ≥ 2φ ( m ), lemma memberikan n ^k = n ^{2φ ( m )} n ^{k - 2φ ( m )} ≡ n ^{φ ( m )} n ^{k - 2φ ( m )} = n ^{k - φ ( m )} ( mod m ) dan kami ulangi sampai eksponen kurang dari 2φ ( m ).

Haskell , 156 byte

(?)membutuhkan dua Integerdetik dan mengembalikan Integer, gunakan sebagai (10^10)?2017(urutan terbalik dibandingkan dengan 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

Cobalah online! (Saya menempatkan case untuk diuji di header kali ini, karena mereka menggunakan notasi eksponensial.)

Anehnya, test case paling lambat bukanlah yang dengan batas kecepatan (itu hampir instan), tetapi yang 524287 ? 32pertama, karena 524287merupakan prime yang jauh lebih besar daripada yang muncul di faktor-faktor dari test case yang lain.

Bagaimana itu bekerja

• (x&m)yadalah x^y `mod` m, atau power mod, menggunakan eksponensial dengan mengkuadratkan.
• n#padalah fungsi totient Euler n, dengan asumsi ntidak memiliki faktor prima yang lebih kecil dari p.
  • madalah ndengan semua pfaktor dibagi keluar.
  • Jika ada kfaktor-faktor seperti itu, totient itu sendiri harus mendapatkan faktor yang sesuai (p-1)*p^(k-1), yang dihitung sebagai div(n*p-n)(p*m).
  • 1`max`...menangani kasus di mana nsebenarnya tidak habis dibagi p, yang membuat argumen lain maxsama dengan 0.
• Fungsi utama m?nmenggunakan itu ketika ycukup besar, n^y `mod` msama dengan n^(t+(y`mod`t)) `mod` m, ketika tadalah total m. ( t+Dibutuhkan untuk faktor n- faktor utama dan mmemiliki kesamaan, yang semuanya dimaksimalkan.)
• Algoritma berhenti karena fungsi total yang diulang akhirnya mencapai 1.

Mathematica, 55 byte

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

Contoh:

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 byte

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

Cobalah online!