Laskeminen alkuluvun moduloarvolla
Laske yhteen ja kerro pysyen modulossa
Laskeminen alkuluvun moduloarvolla on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Miksi moduloa käytetään
Kilpailuohjelmoinnin vastaukset voivat kasvaa valtavan suuriksi ja ylittää reilusti kaikki muualla käytetyt kokonaislukutyypit. Siksi tehtävissä pyydetään usein tulos modulo suuren alkuluvun suhteen, jotta luvut pysyvät pieninä. 🔢
Tunnettu modulo
Useimmin vastaan tuleva alkuluku on 1000000007, joka kirjoitetaan usein muodossa 1e9+7. Se on riittävän suuri törmäysten välttämiseen ja kuitenkin niin pieni, että se mahtuu 64 bittiin.
MOD = 1000000007Mitä modulo tarkoittaa
Modulo-operaattori antaa jakolaskun jäännöksen. Siksi 17 % 5 on 2: luvusta 17 jää 5:llä jaettaessa jäännökseksi 2.
print(17 % 5) # 2Yhteenlasku toimii modulossa
Voitte ensin laskea yhteen ja ottaa modulon vasta lopuksi tai ottaa modulon jokaisessa vaiheessa. Jäännös on kummallakin tavalla sama, joten pienentäkää arvoja usein.
total = (a + b) % MODMyös kertolasku toimii modulossa
Sama sääntö pätee kertolaskuun: ottakaa tulo modulo alkuluvun suhteen. Python käsittelee suuret kokonaisluvut suoraan, mutta modulon ottaminen pitää jokaisen arvon pienenä ja laskennan nopeana.
prod = (a * b) % MODPienentäkää arvoa jokaisen vaiheen jälkeen
Lisätkää pitkässä silmukassa % MOD jokaisella iteraatiolla. Näin luvut eivät kasva valtaviksi ja jokainen operaatio pysyy kevyenä ja ennakoitavana.
ans = (ans * i) % MODVähennyslasku voi tuottaa negatiivisen tuloksen
Vähennyslasku voi tuottaa negatiivisen jäännöksen monissa kielissä. Lisätkää MOD takaisin ennen lopullista moduloa, jotta tulos päätyy ei-negatiiviselle välille 0–MOD-1.
diff = (a - b + MOD) % MODPythonin ystävällinen modulo
Hyvä uutinen: Pythonin % palauttaa positiivisella modulolla aina epänegatiivisen tuloksen. Siksi -1 % 7 antaa tulokseksi 6 eikä -1:tä, eikä tulosta tarvitse korjata erikseen.
print(-1 % 7) # 6Modulo jakautuu laskutoimituksiin
Perusajatus on seuraava: (a op b) % m on sama kuin (a%m op b%m) % m yhteen- ja kertolaskussa. Näin syötteet voi pienentää ennen niiden yhdistämistä.
Jako on poikkeus
Yhteen-, vähennys- ja kertolasku toimivat siististi modulossa. Tavallinen jakolasku ei kuitenkaan toimi, vaan tarvitsette siihen myöhemmin tällä kurssilla modulaarisen käänteisluvun.
Määrittäkää MOD kerran alussa
Määrittäkää MOD vakiona ratkaisunne alussa. Yksi nimetty arvo on parempi kuin lukuisat koodiin hajautetut 1000000007-arvot, joiden sekaan kirjoitusvirhe voi piiloutua.
MOD = 10**9 + 7Pikatarkistus
Miksi MOD lisätään ennen vähennyslaskun tuloksen moduloa?
Kertaus
Osaatte nyt pitää valtavat lukumäärät pieninä käyttämällä alkulukumoduloa, kuten 1e9+7. Ottakaa modulo yhteen-, vähennys- ja kertolaskun jokaisessa vaiheessa, huomioikaa negatiiviset tulokset ja käyttäkää jakoon käänteislukuja. 🎯
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Laskeminen alkuluvun moduloarvolla” ilmainen?
Kyllä – oppitunnin ”Laskeminen alkuluvun moduloarvolla” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Laskeminen alkuluvun moduloarvolla”?
Laske yhteen ja kerro pysyen modulossa Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Laskeminen alkuluvun moduloarvolla”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Laskeminen alkuluvun moduloarvolla
- Nopea modulaarinen potenssilasku
- Modulaarinen käänteisluku Fermat'n avulla
- nCr esilaskettujen kertomien avulla