前言
算术基本定理
对于任何一个大于1的合数，都能分解成有限个质数的乘积
裴蜀定理
存在整数 x，y 使得 
%20%3D%20ax%20%2B%20by%3C%2Ftitle%3E%0A%3Cdefs%20aria-hidden%3D%22true%22%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-67%22%20d%3D%22M311%2043Q296%2030%20267%2015T206%200Q143%200%20105%2045T66%20160Q66%20265%20143%20353T314%20442Q361%20442%20401%20394L404%20398Q406%20401%20409%20404T418%20412T431%20419T447%20422Q461%20422%20470%20413T480%20394Q480%20379%20423%20152T363%20-80Q345%20-134%20286%20-169T151%20-205Q10%20-205%2010%20-137Q10%20-111%2028%20-91T74%20-71Q89%20-71%20102%20-80T116%20-111Q116%20-121%20114%20-130T107%20-144T99%20-154T92%20-162L90%20-164H91Q101%20-167%20151%20-167Q189%20-167%20211%20-155Q234%20-144%20254%20-122T282%20-75Q288%20-56%20298%20-13Q311%2035%20311%2043ZM384%20328L380%20339Q377%20350%20375%20354T369%20368T359%20382T346%20393T328%20402T306%20405Q262%20405%20221%20352Q191%20313%20171%20233T151%20117Q151%2038%20213%2038Q269%2038%20323%20108L331%20118L384%20328Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-63%22%20d%3D%22M34%20159Q34%20268%20120%20355T306%20442Q362%20442%20394%20418T427%20355Q427%20326%20408%20306T360%20285Q341%20285%20330%20295T319%20325T330%20359T352%20380T366%20386H367Q367%20388%20361%20392T340%20400T306%20404Q276%20404%20249%20390Q228%20381%20206%20359Q162%20315%20142%20235T121%20119Q121%2073%20147%2050Q169%2026%20205%2026H209Q321%2026%20394%20111Q403%20121%20406%20121Q410%20121%20419%20112T429%2098T420%2083T391%2055T346%2025T282%200T202%20-11Q127%20-11%2081%2037T34%20159Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-64%22%20d%3D%22M366%20683Q367%20683%20438%20688T511%20694Q523%20694%20523%20686Q523%20679%20450%20384T375%2083T374%2068Q374%2026%20402%2026Q411%2027%20422%2035Q443%2055%20463%20131Q469%20151%20473%20152Q475%20153%20483%20153H487H491Q506%20153%20506%20145Q506%20140%20503%20129Q490%2079%20473%2048T445%208T417%20-8Q409%20-10%20393%20-10Q359%20-10%20336%205T306%2036L300%2051Q299%2052%20296%2050Q294%2048%20292%2046Q233%20-10%20172%20-10Q117%20-10%2075%2030T33%20157Q33%20205%2053%20255T101%20341Q148%20398%20195%20420T280%20442Q336%20442%20364%20400Q369%20394%20369%20396Q370%20400%20396%20505T424%20616Q424%20629%20417%20632T378%20637H357Q351%20643%20351%20645T353%20664Q358%20683%20366%20683ZM352%20326Q329%20405%20277%20405Q242%20405%20210%20374T160%20293Q131%20214%20119%20129Q119%20126%20119%20118T118%20106Q118%2061%20136%2044T179%2026Q233%2026%20290%2098L298%20109L352%20326Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-28%22%20d%3D%22M94%20250Q94%20319%20104%20381T127%20488T164%20576T202%20643T244%20695T277%20729T302%20750H315H319Q333%20750%20333%20741Q333%20738%20316%20720T275%20667T226%20581T184%20443T167%20250T184%2058T225%20-81T274%20-167T316%20-220T333%20-241Q333%20-250%20318%20-250H315H302L274%20-226Q180%20-141%20137%20-14T94%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-61%22%20d%3D%22M33%20157Q33%20258%20109%20349T280%20441Q331%20441%20370%20392Q386%20422%20416%20422Q429%20422%20439%20414T449%20394Q449%20381%20412%20234T374%2068Q374%2043%20381%2035T402%2026Q411%2027%20422%2035Q443%2055%20463%20131Q469%20151%20473%20152Q475%20153%20483%20153H487Q506%20153%20506%20144Q506%20138%20501%20117T481%2063T449%2013Q436%200%20417%20-8Q409%20-10%20393%20-10Q359%20-10%20336%205T306%2036L300%2051Q299%2052%20296%2050Q294%2048%20292%2046Q233%20-10%20172%20-10Q117%20-10%2075%2030T33%20157ZM351%20328Q351%20334%20346%20350T323%20385T277%20405Q242%20405%20210%20374T160%20293Q131%20214%20119%20129Q119%20126%20119%20118T118%20106Q118%2061%20136%2044T179%2026Q217%2026%20254%2059T298%20110Q300%20114%20325%20217T351%20328Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2C%22%20d%3D%22M78%2035T78%2060T94%20103T137%20121Q165%20121%20187%2096T210%208Q210%20-27%20201%20-60T180%20-117T154%20-158T130%20-185T117%20-194Q113%20-194%20104%20-185T95%20-172Q95%20-168%20106%20-156T131%20-126T157%20-76T173%20-3V9L172%208Q170%207%20167%206T161%203T152%201T140%200Q113%200%2096%2017Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-62%22%20d%3D%22M73%20647Q73%20657%2077%20670T89%20683Q90%20683%20161%20688T234%20694Q246%20694%20246%20685T212%20542Q204%20508%20195%20472T180%20418L176%20399Q176%20396%20182%20402Q231%20442%20283%20442Q345%20442%20383%20396T422%20280Q422%20169%20343%2079T173%20-11Q123%20-11%2082%2027T40%20150V159Q40%20180%2048%20217T97%20414Q147%20611%20147%20623T109%20637Q104%20637%20101%20637H96Q86%20637%2083%20637T76%20640T73%20647ZM336%20325V331Q336%20405%20275%20405Q258%20405%20240%20397T207%20376T181%20352T163%20330L157%20322L136%20236Q114%20150%20114%20114Q114%2066%20138%2042Q154%2026%20178%2026Q211%2026%20245%2058Q270%2081%20285%20114T318%20219Q336%20291%20336%20325Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-29%22%20d%3D%22M60%20749L64%20750Q69%20750%2074%20750H86L114%20726Q208%20641%20251%20514T294%20250Q294%20182%20284%20119T261%2012T224%20-76T186%20-143T145%20-194T113%20-227T90%20-246Q87%20-249%2086%20-250H74Q66%20-250%2063%20-250T58%20-247T55%20-238Q56%20-237%2066%20-225Q221%20-64%20221%20250T66%20725Q56%20737%2055%20738Q55%20746%2060%20749Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-3D%22%20d%3D%22M56%20347Q56%20360%2070%20367H707Q722%20359%20722%20347Q722%20336%20708%20328L390%20327H72Q56%20332%2056%20347ZM56%20153Q56%20168%2072%20173H708Q722%20163%20722%20153Q722%20140%20707%20133H70Q56%20140%2056%20153Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-78%22%20d%3D%22M52%20289Q59%20331%20106%20386T222%20442Q257%20442%20286%20424T329%20379Q371%20442%20430%20442Q467%20442%20494%20420T522%20361Q522%20332%20508%20314T481%20292T458%20288Q439%20288%20427%20299T415%20328Q415%20374%20465%20391Q454%20404%20425%20404Q412%20404%20406%20402Q368%20386%20350%20336Q290%20115%20290%2078Q290%2050%20306%2038T341%2026Q378%2026%20414%2059T463%20140Q466%20150%20469%20151T485%20153H489Q504%20153%20504%20145Q504%20144%20502%20134Q486%2077%20440%2033T333%20-11Q263%20-11%20227%2052Q186%20-10%20133%20-10H127Q78%20-10%2057%2016T35%2071Q35%20103%2054%20123T99%20143Q142%20143%20142%20101Q142%2081%20130%2066T107%2046T94%2041L91%2040Q91%2039%2097%2036T113%2029T132%2026Q168%2026%20194%2071Q203%2087%20217%20139T245%20247T261%20313Q266%20340%20266%20352Q266%20380%20251%20392T217%20404Q177%20404%20142%20372T93%20290Q91%20281%2088%20280T72%20278H58Q52%20284%2052%20289Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2B%22%20d%3D%22M56%20237T56%20250T70%20270H369V420L370%20570Q380%20583%20389%20583Q402%20583%20409%20568V270H707Q722%20262%20722%20250T707%20230H409V-68Q401%20-82%20391%20-82H389H387Q375%20-82%20369%20-68V230H70Q56%20237%2056%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-79%22%20d%3D%22M21%20287Q21%20301%2036%20335T84%20406T158%20442Q199%20442%20224%20419T250%20355Q248%20336%20247%20334Q247%20331%20231%20288T198%20191T182%20105Q182%2062%20196%2045T238%2027Q261%2027%20281%2038T312%2061T339%2094Q339%2095%20344%20114T358%20173T377%20247Q415%20397%20419%20404Q432%20431%20462%20431Q475%20431%20483%20424T494%20412T496%20403Q496%20390%20447%20193T391%20-23Q363%20-106%20294%20-155T156%20-205Q111%20-205%2077%20-183T43%20-117Q43%20-95%2050%20-80T69%20-58T89%20-48T106%20-45Q150%20-45%20150%20-87Q150%20-107%20138%20-122T115%20-142T102%20-147L99%20-148Q101%20-153%20118%20-160T152%20-167H160Q177%20-167%20186%20-165Q219%20-156%20247%20-127T290%20-65T313%20-9T321%2021L315%2017Q309%2013%20296%206T270%20-6Q250%20-11%20231%20-11Q185%20-11%20150%2011T104%2082Q103%2089%20103%20113Q103%20170%20138%20262T173%20379Q173%20380%20173%20381Q173%20390%20173%20393T169%20400T158%20404H154Q131%20404%20112%20385T82%20344T65%20302T57%20280Q55%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3C%2Fdefs%3E%0A%3Cg%20stroke%3D%22currentColor%22%20fill%3D%22currentColor%22%20stroke-width%3D%220%22%20transform%3D%22matrix(1%200%200%20-1%200%200)%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-67%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-63%22%20x%3D%22480%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-64%22%20x%3D%22914%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%221437%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-61%22%20x%3D%221827%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%222356%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-62%22%20x%3D%222801%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%223231%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%223898%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-61%22%20x%3D%224954%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-78%22%20x%3D%225484%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2B%22%20x%3D%226278%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-62%22%20x%3D%227279%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-79%22%20x%3D%227709%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=gcd%28a%2Cb%29%20%3D%20ax%20%2B%20by&height=20&id=nTu6F)
数论四大定理
威尔逊定理
(p可以整除(p-1)!+1)
欧拉定理
若n，a为正整数，且n，a互质，则
%7D%20%5C%3B%20%5Cequiv%20%5C%3B%201%20%5C%3B%20(mod%20%5C%3B%20n)%3C%2Ftitle%3E%0A%3Cdefs%20aria-hidden%3D%22true%22%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-61%22%20d%3D%22M33%20157Q33%20258%20109%20349T280%20441Q331%20441%20370%20392Q386%20422%20416%20422Q429%20422%20439%20414T449%20394Q449%20381%20412%20234T374%2068Q374%2043%20381%2035T402%2026Q411%2027%20422%2035Q443%2055%20463%20131Q469%20151%20473%20152Q475%20153%20483%20153H487Q506%20153%20506%20144Q506%20138%20501%20117T481%2063T449%2013Q436%200%20417%20-8Q409%20-10%20393%20-10Q359%20-10%20336%205T306%2036L300%2051Q299%2052%20296%2050Q294%2048%20292%2046Q233%20-10%20172%20-10Q117%20-10%2075%2030T33%20157ZM351%20328Q351%20334%20346%20350T323%20385T277%20405Q242%20405%20210%20374T160%20293Q131%20214%20119%20129Q119%20126%20119%20118T118%20106Q118%2061%20136%2044T179%2026Q217%2026%20254%2059T298%20110Q300%20114%20325%20217T351%20328Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-3C6%22%20d%3D%22M92%20210Q92%20176%20106%20149T142%20108T185%2085T220%2072L235%2070L237%2071L250%20112Q268%20170%20283%20211T322%20299T370%20375T429%20423T502%20442Q547%20442%20582%20410T618%20302Q618%20224%20575%20152T457%2035T299%20-10Q273%20-10%20273%20-12L266%20-48Q260%20-83%20252%20-125T241%20-179Q236%20-203%20215%20-212Q204%20-218%20190%20-218Q159%20-215%20159%20-185Q159%20-175%20214%20-2L209%200Q204%202%20195%205T173%2014T147%2028T120%2046T94%2071T71%20103T56%20142T50%20190Q50%20238%2076%20311T149%20431H162Q183%20431%20183%20423Q183%20417%20175%20409Q134%20361%20114%20300T92%20210ZM574%20278Q574%20320%20550%20344T486%20369Q437%20369%20394%20329T323%20218Q309%20184%20295%20109L286%2064Q304%2062%20306%2062Q423%2062%20498%20131T574%20278Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-28%22%20d%3D%22M94%20250Q94%20319%20104%20381T127%20488T164%20576T202%20643T244%20695T277%20729T302%20750H315H319Q333%20750%20333%20741Q333%20738%20316%20720T275%20667T226%20581T184%20443T167%20250T184%2058T225%20-81T274%20-167T316%20-220T333%20-241Q333%20-250%20318%20-250H315H302L274%20-226Q180%20-141%20137%20-14T94%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-6E%22%20d%3D%22M21%20287Q22%20293%2024%20303T36%20341T56%20388T89%20425T135%20442Q171%20442%20195%20424T225%20390T231%20369Q231%20367%20232%20367L243%20378Q304%20442%20382%20442Q436%20442%20469%20415T503%20336T465%20179T427%2052Q427%2026%20444%2026Q450%2026%20453%2027Q482%2032%20505%2065T540%20145Q542%20153%20560%20153Q580%20153%20580%20145Q580%20144%20576%20130Q568%20101%20554%2073T508%2017T439%20-10Q392%20-10%20371%2017T350%2073Q350%2092%20386%20193T423%20345Q423%20404%20379%20404H374Q288%20404%20229%20303L222%20291L189%20157Q156%2026%20151%2016Q138%20-11%20108%20-11Q95%20-11%2087%20-5T76%207T74%2017Q74%2030%20112%20180T152%20343Q153%20348%20153%20366Q153%20405%20129%20405Q91%20405%2066%20305Q60%20285%2060%20284Q58%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-29%22%20d%3D%22M60%20749L64%20750Q69%20750%2074%20750H86L114%20726Q208%20641%20251%20514T294%20250Q294%20182%20284%20119T261%2012T224%20-76T186%20-143T145%20-194T113%20-227T90%20-246Q87%20-249%2086%20-250H74Q66%20-250%2063%20-250T58%20-247T55%20-238Q56%20-237%2066%20-225Q221%20-64%20221%20250T66%20725Q56%20737%2055%20738Q55%20746%2060%20749Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2261%22%20d%3D%22M56%20444Q56%20457%2070%20464H707Q722%20456%20722%20444Q722%20430%20706%20424H72Q56%20429%2056%20444ZM56%20237T56%20250T70%20270H707Q722%20262%20722%20250T707%20230H70Q56%20237%2056%20250ZM56%2056Q56%2071%2072%2076H706Q722%2070%20722%2056Q722%2044%20707%2036H70Q56%2043%2056%2056Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-31%22%20d%3D%22M213%20578L200%20573Q186%20568%20160%20563T102%20556H83V602H102Q149%20604%20189%20617T245%20641T273%20663Q275%20666%20285%20666Q294%20666%20302%20660V361L303%2061Q310%2054%20315%2052T339%2048T401%2046H427V0H416Q395%203%20257%203Q121%203%20100%200H88V46H114Q136%2046%20152%2046T177%2047T193%2050T201%2052T207%2057T213%2061V578Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-6D%22%20d%3D%22M21%20287Q22%20293%2024%20303T36%20341T56%20388T88%20425T132%20442T175%20435T205%20417T221%20395T229%20376L231%20369Q231%20367%20232%20367L243%20378Q303%20442%20384%20442Q401%20442%20415%20440T441%20433T460%20423T475%20411T485%20398T493%20385T497%20373T500%20364T502%20357L510%20367Q573%20442%20659%20442Q713%20442%20746%20415T780%20336Q780%20285%20742%20178T704%2050Q705%2036%20709%2031T724%2026Q752%2026%20776%2056T815%20138Q818%20149%20821%20151T837%20153Q857%20153%20857%20145Q857%20144%20853%20130Q845%20101%20831%2073T785%2017T716%20-10Q669%20-10%20648%2017T627%2073Q627%2092%20663%20193T700%20345Q700%20404%20656%20404H651Q565%20404%20506%20303L499%20291L466%20157Q433%2026%20428%2016Q415%20-11%20385%20-11Q372%20-11%20364%20-4T353%208T350%2018Q350%2029%20384%20161L420%20307Q423%20322%20423%20345Q423%20404%20379%20404H374Q288%20404%20229%20303L222%20291L189%20157Q156%2026%20151%2016Q138%20-11%20108%20-11Q95%20-11%2087%20-5T76%207T74%2017Q74%2030%20112%20181Q151%20335%20151%20342Q154%20357%20154%20369Q154%20405%20129%20405Q107%20405%2092%20377T69%20316T57%20280Q55%20278%2041%20278H27Q21%20284%2021%20287Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-6F%22%20d%3D%22M201%20-11Q126%20-11%2080%2038T34%20156Q34%20221%2064%20279T146%20380Q222%20441%20301%20441Q333%20441%20341%20440Q354%20437%20367%20433T402%20417T438%20387T464%20338T476%20268Q476%20161%20390%2075T201%20-11ZM121%20120Q121%2070%20147%2048T206%2026Q250%2026%20289%2058T351%20142Q360%20163%20374%20216T388%20308Q388%20352%20370%20375Q346%20405%20306%20405Q243%20405%20195%20347Q158%20303%20140%20230T121%20120Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-64%22%20d%3D%22M366%20683Q367%20683%20438%20688T511%20694Q523%20694%20523%20686Q523%20679%20450%20384T375%2083T374%2068Q374%2026%20402%2026Q411%2027%20422%2035Q443%2055%20463%20131Q469%20151%20473%20152Q475%20153%20483%20153H487H491Q506%20153%20506%20145Q506%20140%20503%20129Q490%2079%20473%2048T445%208T417%20-8Q409%20-10%20393%20-10Q359%20-10%20336%205T306%2036L300%2051Q299%2052%20296%2050Q294%2048%20292%2046Q233%20-10%20172%20-10Q117%20-10%2075%2030T33%20157Q33%20205%2053%20255T101%20341Q148%20398%20195%20420T280%20442Q336%20442%20364%20400Q369%20394%20369%20396Q370%20400%20396%20505T424%20616Q424%20629%20417%20632T378%20637H357Q351%20643%20351%20645T353%20664Q358%20683%20366%20683ZM352%20326Q329%20405%20277%20405Q242%20405%20210%20374T160%20293Q131%20214%20119%20129Q119%20126%20119%20118T118%20106Q118%2061%20136%2044T179%2026Q233%2026%20290%2098L298%20109L352%20326Z%22%3E%3C%2Fpath%3E%0A%3C%2Fdefs%3E%0A%3Cg%20stroke%3D%22currentColor%22%20fill%3D%22currentColor%22%20stroke-width%3D%220%22%20transform%3D%22matrix(1%200%200%20-1%200%200)%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-61%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3Cg%20transform%3D%22translate(529%2C412)%22%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-3C6%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%22654%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMATHI-6E%22%20x%3D%221044%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20transform%3D%22scale(0.707)%22%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%221644%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2261%22%20x%3D%222623%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-31%22%20x%3D%223957%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%224735%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6D%22%20x%3D%225125%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6F%22%20x%3D%226003%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-64%22%20x%3D%226489%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-6E%22%20x%3D%227290%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%227890%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=a%5E%7B%5Cvarphi%28n%29%7D%20%5C%3B%20%5Cequiv%20%5C%3B%201%20%5C%3B%20%28mod%20%5C%3B%20n%29&height=24&id=WIoLb)
孙子定理(中国剩余定理)
费马小定理
引理1
，则 
引理2
内容
质数
试除法判断质数
bool is_prime(int x) {if ( x < 2 ) return false;for (int i = 2; i <= x / i ; i ++ ) if ( x % i == 0 ) return false; // i <= x / i 优化版 <=sqrt(x)return true;}
分解质因数
void divide(int x) {for (int i = 2; i <= x / i ; i ++ ) {if ( x % i == 0 ) {int s = 0;while ( x % i == 0 ) {x = x / i ;s ++ ;}cout << i << " " << s << endl;}}// x 中最多只有一个大于sqrt(x)的质因子if ( x != 1 ) cout << x << " " << 1 << endl;cout << endl;}
筛质数
朴素筛
筛掉所有数的倍数
const int N = 1e6 + 10;int cnt,prime[N];bool st[N];void get_primes(int n) {for (int i = 2; i <= n ; i ++ ) {if (!st[i]) prime[cnt++] = i;for (int j = i + i; j <= n; j += i) st[j] = true;}}
埃式筛
筛掉所有质数的倍数
const int N = 1e6 + 10;int cnt,prime[N];bool st[N];void get_primes(int n) {for (int i = 2; i <= n ; i ++ ) {if (!st[i]) {prime[cnt++] = i;for (int j = i + i ; j <= n; j += i) st[j] = true;}}}
线性筛
用i的最小质因子筛去合数
const int N = 1e6 + 10;int cnt,prime[N];bool st[N];void get_primes(int n) {for (int i = 2; i <= n ; i++ ) {if(!st[i]) prime[cnt ++ ] = i;for (int j = 0;prime[j] <= n / i ; j++) {st[prime[j] * i ] = true;if ( i % prime[j] == 0 ) break;}}}
约数
试除法求约数
vector<int> get_divisors(int x) {vector<int> res;for (int i = 1;i <= n / i; i ++ ) {if ( n % i == 0 ) {res.push_back(i);if ( i != n / i ) res.push_back( n / i );}}sort(res.begin(),res.end());return res;}
约数个数定理
根据乘法原理
#include <bits/stdc++.h>using namespace std;const int mod = 1e9+7;int main(){int n,x;unordered_map<int,int> hash;cin >> n;while (n--) {cin >> x;for (int i = 2;i <= x / i ; i++) {while (x%i==0) {x /= i;hash[i] ++;}}if(x > 1) hash[x]++;}long long res = 1;for (auto i:hash) {res = res * (i.second + 1) % mod;}cout << res << endl;return 0;}
约数和定理
由于约数个数定理可知
#include <bits/stdc++.h>using namespace std;const int mod = 1e9+7;int main(){int n,x;unordered_map<int,int> hash;cin >> n;while (n--) {cin >> x;for (int i = 2;i <= x / i ; i++) {while (x%i==0) {x /= i;hash[i]++;}}if(x>1) hash[x]++;}long long res = 1;for (auto i:hash) {int a = i.first, b = i.second;long long t = 1;while (b--) t = (t*a+1) % mod;res = res * t % mod;}cout << res << endl;return 0;}
欧拉函数
对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目
#include <bits/stdc++.h>using namespace std;int main(){int n,a;cin >> n;while (n--) {cin >> a;int res = a;for (int i = 2; i <= a / i ; i++) {if (a%i==0) {res = res / i * (i-1);while (a%i==0) a = a/i;}}if(a>1) res = res / a * (a - 1);cout << res << endl;}return 0;}
筛法求欧拉函数
phi[pri[j] i] 分为两种情况
phi[pri[j] i] = phi[i] pri[j];
phi[pri[j] i] = phi[i] * (pri[j]-1);
#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int pri[N],phi[N],cnt;bool st[N];long long get_euler(int n) {phi[1] = 1;for (int i = 2; i <= n;i ++) {if(!st[i]) {pri[cnt++] = i;phi[i] = i - 1; // 质数i的欧拉函数为i-1,因为1~i-1都与i互质,共i-1个}for (int j = 0;pri[j] <= n/i;j++) {st[pri[j] * i] = true;if (i % pri[j] == 0) {phi[pri[j] * i] = phi[i] * pri[j];break;}phi[pri[j] * i] = phi[i] * (pri[j]-1);}}long long res = 0;for (int i = 1;i<=n;i++) res+=phi[i];return res;}int main(){int n;cin >> n;cout << get_euler(n) << endl;return 0;}
快速幂
快速幂
求
long long qm(int a,int k) {long long res = 1;while ( k ) {if ( k & 1 ) res *= a;k >>= 1;a *= a;}return res;}
模意义下取幂
求
int qmi(int a,int k,int p) {int res = 1;while (k) {if (k & 1) res = (ll) res * a % p;k >>= 1;a = (ll) a * a % p;}return res;}
快速幂求逆元
#include <bits/stdc++.h>using namespace std;int qmi(int a,int k,int p) {int res = 1;while (k) {if (k&1) res = (long long) res * a % p;k >>= 1;a = (long long) a * a % p;}return res;}int main(){int n,a,p;cin >> n;while (n--) {cin >> a >> p;int ans = qmi(a,p-2,p);if (a%p) cout << ans << endl;else cout << "impossible" << endl;}return 0;}
欧几里得
最大公约数
int gcd(int a,int b) {return b ? gcd(b,a%b) : a;}
扩展欧几里得
求得
int exgcd(int a,int b,int &x,int &y) {if (!b) {x = 1, y = 0;return a;}int r = exgcd(b,a%b,y,x);y -= a / b * x;return r;}
高斯消元
- 遍历每一列c
- 找出当前列中绝对值最大的行
- 把最大行换到上面
- 把该行第一个数变为1（其他数字跟着改变）
- 将下面所有行的当前列都变为0
组合数
从a个不同元素中取出b个元素的所有组合的个数，叫做从a个不同元素中取出b个元素的组合数，记作 
递归法求组合数
根据加法计数原理（当询问次数多，数据小时使用）
void init(){for (int i = 0;i<N;i++) {for (int j = 0;j<=i;j++) {if(!j) c[i][j] = 1;else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;}}}
预处理逆元求组合数
除法用乘以逆元代替，使用快速幂求出逆元
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 100010,mod = 1e9 + 7;int fact[N],infact[N];int qmi(int a,int k,int p) {int res = 1;while (k) {if (k&1) res = (ll) res * a % p;k >>= 1;a = (ll) a * a % p;}return res;}int main(){int n,a,b;cin >> n;fact[0] = infact[0] = 1;for (int i = 1;i<=N;i++) {fact[i] = (ll)fact[i-1] * i % mod;infact[i] = (ll) infact[i-1] * qmi(i,mod-2,mod) % mod;}while (n--) {cin >> a >> b;cout << (ll) fact[a] * infact[b] % mod * infact[a-b] % mod << endl;}return 0;}
卢卡斯定理求组合数
#include <bits/stdc++.h>using namespace std;typedef long long LL;int qmi(int a,int k,int p) {int res = 1;while (k) {if (k&1) res = (LL) res * a % p;k >>= 1;a = (LL) a * a % p;}return res;}int C(int a,int b,int p) {int res = 1;for (int i = 1,j = a;i<=b;i++,j--) {res = (LL) res * j % p;res = (LL) res * qmi(i,p-2,p) % p;}return res;}int lucas(LL a,LL b,int p) {if (a<p and b<p) return C(a,b,p);return (LL) C(a%p,b%p,p) * lucas(a/p,b/p,p) % p;}int main(){int n,p;LL a,b;cin >> n;while (n--) {cin >> a >> b >> p;cout << lucas(a,b,p) << endl;}return 0;}
分解质因数法求组合数
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
- 筛法求出范围内的所有质数
- 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + …
- 用高精度乘法将所有质因子相乘
#include <iostream>#include <vector>using namespace std;const int N = 5010;int primes[N], cnt, sum[N];bool st[N];void get_primes(int n) {for (int i = 2; i <= n; i++) {if (!st[i]) primes[cnt++] = i;for (int j = 0; primes[j] <= n / i; j++) {st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}}int get(int a, int p) {int res = 0;while (a) {res += a / p;a /= p;}return res;}vector<int> mul(vector<int> &a, int k) {vector<int> res;int t = 0;for (int i = 0; i < a.size(); i++) {t += a[i] * k;res.push_back(t % 10);t /= 10;}while (t) {res.push_back(t % 10);t /= 10;}return res;}int main() {int a, b;cin >> a >> b;get_primes(a);for (int i = 0; i < cnt; i++) {int p = primes[i];sum[i] = get(a, p) - get(a - b, p) - get(b, p);}vector<int> res = {1};for (int i = 0; i < cnt; i++) {for (int j = 0; j < sum[i]; j++) {res = mul(res, primes[i]);}}for (int i = res.size() - 1; i >= 0; i--) cout << res[i];cout << endl;return 0;}
卡特兰数
给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： 
#include <iostream>using namespace std;typedef long long LL;const int mod = 1e9 + 7;int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = (LL) res * a % p;a = (LL) a * a % p;k >>= 1;}return res;}int main() {int n;cin >> n;int a = 2 * n, b = n;int res = 1;for (int i = a; i > b; i--) res = (LL) res * i % mod;for (int i = 1; i <= b; i++) res = (LL) res * qmi(i, mod - 2, mod) % mod;res = (LL) res * qmi(n + 1, mod - 2, mod) % mod;cout << res << endl;return 0;}
容斥原理
奇加偶减
Nim游戏(博弈论)
Mex运算
设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S
SG函数
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
简单Nim游戏
把所有堆石子数异或，非0先手必胜，反之必败
先手把异或出来的石子数拿去后，剩下石子位位相对，只要每次取与对手相同的石子数，对手必先碰到石子数为0的情况
#include <bits/stdc++.h>using namespace std;int main(){int n,x;cin >> n;int res = 0;while (n--) {cin >> x;res ^= x;}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;}
台阶Nim游戏
每一层取走是放在下一层的，第0层是不能操作的，所以当某个人只能操作第0层时就输了。
那先手玩家只需要管奇数层即可，同简单Nim游戏
#include <bits/stdc++.h>using namespace std;int main(){int n,x;int res = 0;cin >> n;for (int i = 1;i<=n;i++) {cin >> x;if (i%2) res ^= x;}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;}
集合Nim游戏
#include <bits/stdc++.h>using namespace std;const int N = 110, M = 10010;int s[N],f[M],n,m;int sg(int x) {if(f[x]!=-1) return f[x];unordered_set<int> S;for (int i = 0;i<n;i++) {if (x>=s[i]) S.insert(sg(x-s[i]));}for (int i = 0;;i++) {if (!S.count(i)) return f[x] = i;}}int main(){cin >> n;for (int i = 0;i<n;i++) cin >> s[i];cin >> m;int res = 0;memset(f,-1,sizeof f);for (int i = 0;i<m;i++) {int x;cin >> x;res ^= sg(x);}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;}
拆分Nim游戏
#include <bits/stdc++.h>using namespace std;const int N = 110;int f[N],n;int sg(int x) {if (f[x]!=-1) return f[x];unordered_set<int> S;for (int i = 0;i<x;i++) {for (int j = 0;j<=i;j++) {S.insert(sg(i) ^ sg(j));}}for (int i = 0;;i++) {if(!S.count(i)) return f[x] = i;}}int main(){cin >> n;memset(f,-1,sizeof f);int res = 0;for (int i = 0;i<n;i++) {int x;cin >> x;res ^= sg(x);}if (res) cout << "Yes" << endl;else cout << "No" << endl;return 0;}
若有收获，就点个赞吧
0 人点赞
