Մոդուլյար թվաբանություն (Modular arithmetic)
Շատ դեպքերում մեզ չի հետաքրքրում գործողության արդյունքի բացարձակ արժեքը, այլ միայն այն, թե ինչ մնացորդ է ստացվում այդ արդյունքը
m-ի վրա բաժանելիս: Այսինքն, մենք հաշվում ենք արդյունքը մոդուլո m:Հետաքրքիր է, բայց մենք ամեն օր գործ ենք ունենում մոդուլյար թվաբանության հետ, օրինակ՝ ժամացույց նայելիս: Մեզ հարկավոր չէ տվյալ պահի ամբողջական ժամը (սկսած տարվա սկզբից կամ անգամ Մեծ Պայթյունից հետո անցած ժամանակից), այլ պարզապես օրվա ժամը, որն ըստ էության «ժամացույցի» արժեք է մոդուլո 12 կամ մոդուլո 24 (կախված ձևաչափից): Այսինքն՝ ժամանակի ընթանալու հետ ժամացույցը 0-ից դառնում է 1, հետո 2, 3, … մինչև 11, ապա նորից 0: Այդ գործընթացը կրկնվում է անդադար, և ժամի արժեքը միշտ ընկած է 0-ից 11 թվերի միջև: Եթե տրված է տարվա սկզբից անցած ժամերի որևէ թիվ
h, օրվա ժամը կգտնենք h % 12 արտահայտությամբ (կամ, եթե 24-ժամյա ձևաչափ է, ապա h % 24):
Երբ ուշադրություն ենք դարձնում թվի վերջին թվանշանին, կարող ենք այն դիտարկել որպես «ժամացույց» 10 կետերով՝ 0, 1, 2, …, 9, որոնք ներկայացնում են հնարավոր բոլոր թվանշանները: Եթե թվին ավելացնում ենք 1, նրա վերջին թվանշանն ավելանում է 1-ով, մինչև հասնի 9-ին, որից հետո, ևս 1 ավելացնելիս, վերջին թվանշանը վերադառնում է 0-ին: Կամայական տրված
n թվի համար, մենք կարող ենք գտնել դրա վերջին թվանշանը n % 10 արտահայտությամբ (10-ի բաժանելուց ստացվող մնացորդը):Եթե դիտարկում ենք բիթերը (0 և 1), ապա կարելի է պատկերացնել «ժամացույց» միայն 2 կետով՝ 0 և 1: Երբ 0-ին ավելացնենք 1, ստանում ենք 1, իսկ երբ 1-ին ավելացնենք 1, կստանանք 0: Կամայական տրված բիթային
n թվի համար, վերջին բիթը կարելի է պարզել n % 2 արտահայտությամբ (2-ի բաժանելուց ստացվող մնացորդը):Այսպիսով, մոդուլյար թվաբանությունն ըստ էության «ժամացույց» է, որը բաղկացած է
m կետերից (օրինակ՝ m-ը 12 է ժամերի համար, m-ը 10 է թվանշանների համար և m-ը 2 է բիթերի հետ աշխատելիս): m-ը կարող է լինել ցանկացած թիվ, և որոշ խնդիրներ պահանջում են հաշվել արդյունքը ըստ ինչ-որ մեծ պարզ թվի (օրինակ ) վրա բաժանելուց ստացվող մնացորդի։ Այսպիսի պարզ թվեր սովորաբար վերցնում են, որպեսզի համոզված լինեն, որ հաշվարկները ճիշտ են կատարված։Գումարում մոդուլո m
Երբ գումարում ենք երկու թվեր
a և b և ցանկանում ենք արդյունքը մոդուլո m-ով ստանալ, օրինակ՝ երբ պետք է գտնել վերջին թվանշանը (մոդուլո 10-ով), կարող ենք բավականին հեշտացնել հաշվարկը: Նախ a-ի և b-ի արժեքները վերցնում ենք մոդուլո m-ով, ապա գումարում և նորից վերցնում արդյունքը մոդուլո m-ով: Սա կարելի է գրել որպես res = (a % m + b % m) % m.Հանում մոդուլո m
Երբ հանում ենք
b-ն a-ից մոդուլո m-ով, կարելի է այն ընկալել որպես ժամացույցը «հետ տալ» b ժամ սկսած ժամանակի a պահից: Օրինակ, 5-ից սկսած հետ տալ ժամը 2 ժամով (5 - 2) % 12 = 3, իսկ 5-ից սկսած հետ տալ ժամը 7 ժամով (5 - 7) % 12 = -2 % 12 = 10: Կարող ենք նաև հանել թվեր, որոնք մեծ են m-ից, նախապես վերցնելով դրանց m-ի վրա բաժանելիս ստացվող մնացորդը: Օրինակ՝ (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3:Որոշ ծրագրավորման լեզուներում (ինչպես Python-ը)
% օպերատորը միշտ վերադարձնում է ոչ բացասական մնացորդ, բայց ուրիշ լեզուներում (ինչպես օրինակ C++ը) արդյունքը կարող է բացասական ստացվել: Հետևաբար, երբ կարևոր է միշտ ոչ բացասական արժեք ստանալ, անհրաժեշտության դեպքում պետք է արդյունքին գումարել m (օրինակ, -2-ին գումարում ենք 12 և ստանում ենք 10): Սա կարող եք ընկալել որպես ժամացույցը կրկին առաջ տանել մեկ լրացուցիչ օրով, որը չի փոխում ցուցադրվող ժամը:Բազմապատկում մոդուլո m
Երբ բազմապատկում ենք երկու թվեր մոդուլո
m-ով, վերջնական արդյունքը ևս կարելի է վերցնել մոդուլո m-ով: Եթե, օրինակ, m = 10, ապա դրա միջոցով մենք կարող ենք պարզել երկու թվի արտադրյալի վերջին թվանշանը:Բաժանում մոդուլո m
Բաժանումը մոդուլո
m-ով ավելի բարդ է, քան նախորդ գործողությունները: Ենթադրելով, որ խոսքը կրկին վերջին թվանշանի մասին է (մոդուլո 10), օրինակ՝ 28-ը բաժանել 7-ի, ստանում ենք 4, որի վերջին թվանշանը նույնպես 4 է: Բայց եթե պարզապես վերցնենք 28-ի և 7-ի վերջին թվանշանները (8 և 7), ակնհայտ չէ, թե ինչպես ստանալ 4: Դա կարելի է անել Էյլերի թեորեմի կիրառմամբ, որի համառոտ բացատրությունը կարող եք գտնել այստեղ՝ https://cp-algorithms.com/algebra/module-inverse.html:Առաջադրանք. Հաշվել -ը m-ի վրա բաժանելիս ստացվող մնացորդը
Ձեզ խնդրում են հաշվել արժեքը, որտեղ
x, n և m-ը տրված են մուտքում:Մուտք
Մուտքի միակ տողը պարունակում է երեք ամբողջ թիվ
x, n (1 ≤ n ≤ ), և m (1 ≤ x, m ≤ ):Ելք
Ծրագիրը պետք է տպի -ի արդյունքը:
Օրինակներ
Input | Output |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB