Contact și feedback

Nu obții 100 de puncte sau ai nelămuriri în privința problemelor? Scrie-mi pe Instagram.


Ai găsit o greșeală, vrei să raportezi un utilizator sau vrei să comunici altceva? Folosește formularul de contact.


Vrei să ne transmiți o părere despre platformă? Folosește formularul de feedback.

Shortcuturi

Folosește următoarele shortcuturi pentru a naviga mai ușor pe platformă.

Generale

Meniu shortcuturi?
Căutare probleme sau utilizatori/
Navigare printre rezultatele căutării↑, ↓
Meniu de contact și feedbackCTRL + Shift + F
Ieșire din meniuriEsc

Editor probleme

Setări editorCTRL + Shift + S
Schimbare stil editorCTRL + Shift + E
Șabloane de codCTRL + Shift + 1/2/3
Golire editorCTRL + Shift + 4

De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?

Cel mai cu seamă ai rezolvat o problemă de informatică (cum ar fi de combinatorică sau de programare dinamică) și în cerința acesteia apărea mențiunea de a afișa răspunsul modulo 666013, modulo 1.000.000.007, modulo 123457 sau un alt număr foarte ciudat (care pare ales la întâmplare). Această mențiune nu este una făcută la întâmplare, ci ajută foarte mult la implementarea problemei și la verificarea acesteia.

De ce se cere răspunsul modulo un număr mare?

Răspunsul pentru anumite probleme poate fi uriaș. Spre exemplu, dacă vrem să calculăm n! (factorialul unui număr n), trebuie să înmulțim pe rând numerele 1, 2, 3, …, n, număr ce poate avea un număr uriaș de cifre. Doar factorialele până la 12! încap în tipul de date int, iar doar până la 20! încap în tipul de date long long.

Astfel, o problemă care cere calcularea numărului de permutări al unei mulțimi, de pildă, se așteaptă la calcularea valorii n!, unde n este lungimea mulțimii. Prin urmare, există doar câteva opțiuni la care poate să recurgă creatorul unei probleme:

  • să folosească valori mici pentru n (n ≤ 20), ca să se utilizeze tipurile de date int sau long long, care ar face problema prea ușoară;
  • să implementeze soluția pe numere mari care să afișeze răspunsul exact pentru valori mai mari de 20, lucru ce ar încetini considerabil programul și l-ar complica fără rost;
  • să folosească un alt artificiu care să poată folosi tipurile de date cunoscute dar să accepte și numere mai mari de 20.

Artificiul care se poate utiliza în acest caz este efectuarea operațiilor pe aritmetica modulară. Mai exact, toate operațiile pe care le facem (adunări, scăderi, înmulțiri, împărțiri, etc.) se realizează modulo un anumit număr mai mare mod, dar care încape în int. În acest fel, mereu vom avea un răspuns între 0 și mod - 1.

Mai mult decât atât. Există cazuri în care dacă efectuăm operații modulo mod, vom ajunge într-un final la răspunsul 0, lucru ce ar însemna că dacă cineva nu știe să rezolve o problemă, ar putea afișa 0 și ar primi un pic de punctaj pe testele care au ca răspuns 0. Pentru a evita acest lucru, numărul mod trebuie să fie prim.

De ce se aleg valori aleatorii? De ce nu modulo 10000?

Valorile alese pentru mod nu sunt aleatorii. Acestea trebuie să îndeplinească condițiile:

  • să fie foarte mari;
  • să fie numere prime;
  • să fie ușor de reținut (pentru a evita încurcăturile).

Din acest motiv se folosesc cel mai des următoarele numere pentru mod: 666013, 1.000.000.007, 123457, 777013, 1.000.000.009 și altele.

Și totodată de aceea nu apar numere mai obișnuite, precum puteri de 10 (1000, 100.000, etc.) sau alte numere.

Cum se aplică operațiile modulo 666013?

Operațiile modulo 666013 (sau alt număr) nu sunt foarte dificile. Pentru generalizare, numim valoarea la care se calculează restul mod. Iată cum se fac operațiile obișnuite.

Adunarea modulară

Adunarea este foarte simplă. Operația s = x + y în modulo este:

//Opțiunea 1
s = (x + y) % mod;

Sau, mai sigur, ca să ne asigurăm că nu ieșim din tipurile de date:

//Opțiunea 2. Îl facem long long și aplicăm modulo la toate numerele
s = (1ll * (x % mod) * (y % mod)) % mod;

Scăderea modulară

Scăderea este asemănătoare, însă trebuie avut grijă atunci când rezultatul ajunge negativ (ceea ce este un lucru obișnuit în aritmetica modulară). Ne amintim că rezultatul trebuie să fie între 0 și mod - 1, deci adunăm un mod dacă este nevoie.

//Opțiunea 1
dif = x - y;
while(dif < 0) {
    dif = dif + mod;
}

Sau, dintr-o singură linie:

//Opțiunea 2. Adunăm direct mod
dif = (x - y + mod) % mod;

Înmulțirea modulară

Înmulțirea este similară cu adunarea. Dacă vrem să aplicăm p = x * y, avem:

//Opțiunea 1
p = (x * y) % mod;

Sau a doua opțiune, mai sigură:

//Opțiunea 2
p = (1ll * (x % mod) * (y % mod)) % mod;

Împărțirea modulară

Împărțirea modulară poate fi mai complicată. Să zicem că vrem să facem împărțirea 666014 / 2 modulo 666013. Răspunsul pare simplu, e 333007 modulo 666013, adică 333007. Dar dacă facem cum am făcut până acum, adică (666014 % 666013) / (2 % 666013), avem 1 / 2, adică un număr cu virgulă, care este clar diferit de răspunsul corect 333007.

Așadar, nu acesta este răspunsul. Defapt, împărțirea de tip n = x / y este echivalentă cu n = x * puterelog(y, mod - 2). Funcția puterelog este ridicarea la putere, care trebuie implementată în timp logaritmic pentru eficiență și totodată trebuie realizată modulo mod.

n = x * puterelog(y, mod - 2);

Alte operații pe aritmetică modulară

Alte operații se pot dezvolta după cele menționate mai sus. De pildă, calculul combinărilor, aranjamentelor, permutărilor, etc. se implementează cu ușurință folosind aceste reguli.

Alte resurse și bibliografie

Obține medalia mult dorită. Devino As la olimpiadă.

Curs complet de olimpiadă, pregătit de olimpici de la Oxford și TU Delft.

Cuprinsul lecției

Se încarcă…

Citește și

Funcții predefinite în C++ (matematice, șiruri de caractere)Numere triunghiulare. Verificarea unui număr triunghiularCăutare binară în C++Divide et Impera (metodă de programare C++)Cel mai mic număr cu suma cifrelor N în C++Instrucțiunea continue (structuri repetitive)Numărul combinărilor în C++ (formula combinărilor)Ce este o funcție void în C++?Suma divizorilor unui număr în C++Numărul de apariții al unui număr într-un vector în C++Afișarea elementelor unui vector recursiv în C++Tipuri de date în C++: numere întregi, reale, caractere și alteleMatrice Fibonacci - al n-lea termen Fibonacci în timp logaritmicMaximul și minimul a n valori în C++Tipul struct în C++. Ce sunt structurile de date neomogeneInstrucțiunea for (structuri repetitive)Suma 1 + 2 + 3 + ... + N în C++Numărul permutărilor în C++ (formula permutărilor)Interschimbarea a două variabile în C++ (3 metode)Complexitatea unui algoritm (timp și spațiu) în C++Suma divizorilor numerelor de la 1 la N (Folosind ciurul lui Eratostene)Maximul și minimul a trei valori în C++Codul ASCII (tabel complet)Transformarea unui număr din baza 2 în baza 10 în C++Transformarea unei litere mici în literă mare în C++Cel mai mare divizor comun (CMMDC) a două numere în C++Mediana unui șir de valori în C++Distanța dintre două puncte în C++Combinatorică în C++: permutări, aranjamente, combinări și alteleNumărul de divizori primi ai unui număr în C++Indicatorul lui Euler al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Instrucțiunea break (structuri repetitive)Ciurul lui Eratostene în C++Suma elementelor unui vector recursiv în C++Șirul lui Fibonacci în C++Numărul de cifre ale factorialului unui numărVerificare dacă șir de caractere este palindrom în C++Indicatorul lui Euler în C++Factorialul unui număr în C++Verifică dacă o literă este mică sau mare în C++Comentarii în C++Bordarea unei matrice în C++Funcții în C++. Ce sunt subprogrameleGenerarea șirului Fibonacci generalizat în C++Numărul de divizori al unui număr în C++Valoarea absolută (modulul) unui număr în C++Rădăcina cubică a unui număr în C++ (cube root)Al N-lea termen Fibonacci în C++CMMDC recursiv a două numere naturale în C++Cifrele unui număr. Prelucrarea cifrelor unui număr în C++Transformarea unui număr din baza 10 în baza 2 în C++Cel mai frecvent element dintr-un șir în C++Ce este o variabilă unsigned în C++?Structuri repetitive (while, do while, for, etc)Instrucțiunea de decizie în C++: if, else, switch, caseVerifică dacă un număr dat este o putere de 2 în C++Cifra maximă și minimă a unui număr în C++Cel mai mic/mare divizor prim al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Al N-lea termen dintr-o progresie aritmeticăOglinditul unui număr în C++Aria și circumferința unui cerc în C++Verifică dacă un număr aparține șirului Fibonacci în C++Cel mai semnificativ bit în C++Cum să afișezi partea întreagă a unui număr real în C++Ce înseamnă endl în C++?Vectorii în C++: declarare și parcurgereȘiruri de caractere în C++. Tot ce trebuie să știiNumărul de divizori al numerelor de la 1 la N (Folosind ciurul lui Eratostene)Copiuțe: Cifrele unui numărCel mai puțin semnificativ bit în C++Materia pentru olimpiada de informatică - tot ce trebuie să știiVerifică dacă un bit de pe o anumită poziție este 1 sau 0 în C++Al N-lea termen dintr-o progresie geometricăAlgoritm recursiv pentru căutare binară (clasa a X-a)Oglinditul recursiv al unui număr în C++Radicalul unui număr în C++ (rădăcina pătrată)Instrucțiunea while (structuri repetitive)Maximul și minimul a două valori în C++Verificarea unui an bisect în C++Verificare număr prim în C++ (Clasa a IX-a)Sortare crescătoare recursivă în C++ - Merge sort și Bubble sortTutorial instalare CodeBlocks (ușor) - Introducere în informatică C++Aria unui triunghi folosind coordonatele acestora în C++Vectorii în C++: citire și afișareVerifică dacă un caracter este cifră în C++Recursivitate în C++Verifică dacă un caracter este literă în C++Cifra maximă a unui număr recursiv în C++Prima cifră a unui număr în C++Numărul aranjamentelor în C++ (formula aranjamentelor)Verifică dacă o literă este vocală în C++Interclasarea a doi vectori în C++Citirea și afișarea matricelor în C++Verifică dacă trei puncte sunt coliniare C++Ridicarea la putere în timp logaritmic în C++. Exponențiere rapidăNumărul minim de peroane pentru o gară în C++Cum să citești și să afișezi în fișiere în C++Aplicații cu ciurul lui Eratostene în C++: suma divizorilor, numărul divizorilorAfișarea divizorilor primi ai unui număr în C++Instrucțiunea do while (structuri repetitive)De ce cer unele probleme răspunsul modulo 666013 sau modulo 1.000.000.007?Inversarea unui vector în C++Pointer în C++. Variabile de tipul char * (char steluță)Suma numerelor naturale dintr-un interval dat în C++Inversarea unui șir de caractere în C++Verifică dacă un număr este par sau impar fără modulo în C++Calculul combinărilor de n luate câte k (nCk) în C++Verificare dacă un număr este palindrom în C++Matrice în C++. Declararea și parcurgerea tablourilor bidimensionaleMaximul și minimul unui vector în C++Do while vs while în C++ - Care e diferența?Cum să calculezi instant 2 la puterea N în C++Matrice pătratice în C++. Diagonala principală și secundarăCâte numere naturale sunt într-un interval dat? (C++)Operații cu numere mari în C++ - Toate funcțiile explicateCe înseamnă variabilă globală și locală în C++?Cea mai lungă secvență de elemente crescătoare în C++Cifra de control a unui numărTransformarea unei litere mari în literă mică în C++CMMMC a două numere în C++ (cel mai mic multiplu comun)Aflarea sumei primelor N sume GaussCitește un șir de caractere cu spații în C++Vectori de frecvență (de apariții) în C++Află secolul unui an citit de la tastatură în C++

© Drepturi de autor

Echipa InfoAs își rezervă drepturile de autor pentru conținutul acestei pagini. Copierea conținutului fără acordul scris expres al InfoAs reprezintă o încălcare a Legii 8/1996 și va fi tratată ca atare.

Trimite lecția

Toată lecția

Doar videoclipul pe YouTube

Informatica devine ușoară cu InfoAs

Intră în cont