A^b^c (mod 1000000007) problemi

Merhabalar,
Yakın zamanda çözdüğüm bir problemi sizinle paylaşmak istiyorum. Çok hoşuma giden çıtır problemlerden biri. Sizlerden de çözümler almak isterim doğrusu.

Hayırlı kodlamalar :last_quarter_moon_with_face: :first_quarter_moon_with_face: :upside_down_face:

Bakmak isteyenler için ipucu

Fermatın küçük teoremini kullan.

Buyrun benim çözümüm de burada. https://paste.ubuntu.com/p/6Ztd6VQYWD/

1 Beğeni

Bu c dili ile mi yazılmış

Cin i görünce aklıma o geldi

Cozum C++ ile yapilmis.

Şöyle bir yol izledim:

def mod(*args, base):
    return args[0] ** mod(*args[1:], base=base) % base if args else 1


assert mod(3, 7, 1, base=10 ** 9 + 7) == 2187
assert mod(15, 2, 2, base=10 ** 9 + 7) == 50625
assert mod(3, 4, 5, base=10 ** 9 + 7) == 763327764
1 Beğeni
def solution(a, b, c):
    return a**b**c % (10**9 + 7)

for i in range(int(input())):
    print(solution(*map(int, filter(None, input().split(" ")))))
1 Beğeni

Merhabalar, ilgileriniz için hepinize teşekkür ediyorum. @EkremDincel ve @dildeolupbiten hocalarımın kodlarını kendi bilgisayarımda python idle’ında aşağıdaki input için denedim .

1
1000000000 1000000000 1000000000 

sonuçta problemde
a, b, c <= 10^9 ifadesi var.
Ben kendi kodumu çalıştırdım output olarak

497489713

verdi, ama sizin kodlar 1 sn limitini aştı. (TLE verdi.)

Şu noktayı söylemem lazım, 1000000007 sayısı asal bir sayıdır. Competitive programmingte sık sık kullanılır.

@dildeolupbiten hocam, fonksiyonunuzdaki base değeri zaten belli, 1000000007 . base parametresine gerek yok.

İyi akşamlar dilerim.

Ben sizin kodunuza şunu girince:

2
18446744073709551617 18446744073709551617 18446744073709551617

şu çıktıyı alıyorum:

291172003
291172003

Linkini verdiğiniz soruda da ne tür parametreler ile 1 saniyenin altında cevap verilmesi gerektiğini göremedim. En başta dediğiniz gibi kısayollar kullanmak genel olarak daha verimli çalışabilir.

O base’i hard coded olmasın diye yazdım.

Hocalarım merhaba,

Kusura bakma hocam dediğini tam anlayamadım ama anladığım kadarıyla yazayım:

Şimdi inputlar şunlar olacak.
n -> test sayısı
a, b, c -> her test için sırasıyla a, b, c değerleri

a, b, c <= 10^9
n in hangi aralıkta olduğu yazılmamış (mesela n <= 2 * 10^5 mi yoksa 3 * 10^5 mi gibi)

bahsettiğiniz time ve memory limit ise onları mavi ile işaretledim hocam.

Saygılar abi :tophat:, ama eğer o base asal olmazsa soru a, b, c <= 10^9 için çözülemez :slight_smile:

Bu arada istiyorsanız çözümü de anlatabilirim. Ya da yazdığım kod anlaşılmıyorsa python ile de yazabilirim, vaktinizi öldürüyorsam kusuruma bakmayın, ama inanın çözümü öğrenince kazanan siz olacaksınız.

İyi geceler dilerim sizlere.

1 Beğeni

Estağfurullah, tabi anlatabilirsiniz. Yeni bir bakış açısı öğrenmiş oluruz.

1 Beğeni
O zaman bakmak isteyenler için çözüm

10^9 + 7 asal sayıdır. Şimdi ilk olarak
m = 10^9 + 7 diyelim.
a^n mod m = (a mod m)^n mod m
olduğu için
a^b^c mod m = (a mod m)^b^c mod m olur.
Kısaca a = a mod m diyorum.

Daha sonra ise m asal sayı olduğu için Fermat’ın küçük teoreminden

a^(m - 1) mod m = 1
olmalı. Bunu şöyle kullanıyorum.
b^c = mod(m - 1)
Bunu da şöyle açıklayayım.
4^15 mod(7) nedir diye soralım.
4^15 = 4^6 * 4^6 * 4^3 mod(7) = 1 * 1* 4^3 mod(7) = 64 mod(7) = 1

İşte bu fikirle yukarıdaki b^c nin m - 1 e göre modunu alıyorum. Burayı anladıysanız son olarak kısaca şöyle toparlayayım.

m = 10^9 + 7
a %= m
b %= m - 1
x = b^c mod(m - 1)
sonuc = a^x mod m
print(sonuc) 

İlgi gösterdiğiniz için teşekkür ederim :heart:

2 Beğeni

Lise zamanlarında büyük sayılarla alakalı bazı formüller ezberlemiştik (öğrenmemiştik) ama işte zaman içinde kullanmayınca, bir de öğrenmek yerine ezber yapınca unutuluyor. Yoksa Python’ın 1000000000 ** 1000000000 ** 1000000000 işleminin sonucunu hesaplamasını beklemek çılgınca.

1 Beğeni

Hocam mesela atıyorum
x *y çok büyük bir sayı çıkıyorsa mod alıyorlar bunun için 10^9 + 7 asalını kullanıyorlar. Genelde böyle sorularda çözümün modu isteniyor, yoksa dediğiniz gibi bilgisayar Allah bilir ne zaman hesaplar.

x * y mod m = (x mod m) * (y mod m) mod m gibi formüller kullanıyorlar bu iş için.

Ben de bazen formülleri unutuyorum, genelde nette arama yapıyorum şahsen :slight_smile:

edit: Atıyorum (a / b) mod m diyorum modular inverse kavramı çıkıyor karşıma.

Hesaplamasından ziyade kaynak yeter mi?

import sys

for i in range(100000000):
    print(f"i = {i}, size = {sys.getsizeof(i ** i ** i)} bytes")

Çıktı:

i = 0, size = 24 bytes
i = 1, size = 28 bytes
i = 2, size = 28 bytes
i = 3, size = 32 bytes
i = 4, size = 96 bytes
i = 5, size = 992 bytes
i = 6, size = 16108 bytes
i = 7, size = 308288 bytes
i = 8, size = 6710912 bytes

Daha dokuzuncu adımda 6 MB’lık bir veri oluşuyor. :p.

2 Beğeni