思路如下:

如果 $bx \equiv a \pmod{p}$

那么就有 $bx\times inv(a) \equiv 1 \pmod{p}$

那么先求$inv(a) \pmod{p}$

然后利用$x \times b\cdot inv(a) + y \cdot p = 1$求解x即可

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod =19260817;
ll res,x,y,tx,ty;
ll n,m;

void getnm(){
	string s1,s2;
	cin>>s1>>s2;
	for(int i=0;i<(int)s1.length();i++){
		n=n*10+(s1[i]-'0');
		n%=mod;
	}
	for(int i=0;i<(int)s2.length();i++){
		m=m*10+(s2[i]-'0');
		m%=mod;
	}
}
void exgcd(ll a,ll b){
	if(b==0){
		x=1,y=0;
		res=a;
	}
	else{
		exgcd(b,a%b);
		tx=x,ty=y;
		x=ty;
		y=tx-(a/b)*ty;
	}
}
int main(){
	getnm();
	if(m==0){
		cout<<"Angry!";
		return 0;
	}
	//cout<<n<<' '<<m<<'\n';
	exgcd(n,mod);
	exgcd(m*x,mod);
	cout<<(x%mod+mod)%mod;
	return 0;
}

WA#6正解与错解

输入:

8012676981885610592934689617146394506210952648951741185000757600900122534982152770136952112927302677139876602569901411879820035779315953943351145295149927032160914578787298334962732645496673115188443592649579549751823720914735416361151442678283329311724902946941620560406460942895475339356765155916715018046933976156311930309724975309942847503299385175143353512689293535652984747447125738317810938586201022409261052894300115768267621719817041685642551051230059089489357842774982904141870773912851043102738465418035246996086941460895372030271151683855566419458032446469737260228902623828686617160371529593283510750801843945981137931424015792248451146311092823914899875714748727854259205262095046988617599832354485268847274343128010647410216710542421409447060326942135614374217741293778777479751993320367612651056586896989838416190592276699988257379035717570597260628872403110926449814571318741411854477397695715570262752044077484449416892279990076746761393666239465555299530808759563671635174577611620100202254774178414504793985769328321816878994740253950247476052886495529401542746213006984754244388294838901505871395167969837038887563125504701377741132772758642363447554921991248318425839247099525417137724971522714528984262383174245112227389483682103265640572339078983398506631061384353902323483904925558895192934673286332892973120131614073164411999529540725694761709544615078702586662854266672588013461937733791806356488918461142835411929057356882611633047591162233028407309518957271772481826938315203664449366877476241017111893730109300476119875592830904266335838292595621320674028134198878881802672302055785491213984994814938154492839297143971842152562056257084839903937216954835445910623200958604110928217790047912063573670900283840690874569923257440875638649981169623924693570298074258686700603166986882280459962507000328228619824968343974049089358903841165335648732566827281264830162672444177536360714652042141861406532892429293079582006368102036312430727812962529462719229430026853076038098730659667382919730026767962812085662667643296209144300489122264299736776841618892287543599273932023911179210585394434803786277998444423588235510774027470914075184702524119293924115135131528648960925417941239152752931694126052322383057882922666554439112726868089546552624012266020058845249272501679023654755554002089447437981189753857824807989017661782697288943781082002326419681050104134102518221627686823295597827629855662014736474567539359598949799361258241644913402355195563175204826012024909574155394349391923039377811837882794600409377074803449147341280695090960944364985337129568618165687401141427655553602503480037017139472034452605607608963888730645742709498165125943822614070861039412917038035319318895751006220783958880265742131140491601050003490722003586539633899465787057064884995189973083956162243791289032004411486409678569469178278596395785196204825759218204539398879395127473772329888839582246729950875611751038380705957094913988020199352105294684219320695028575048468149511831869974631980233892825492185706182109928970786994288757049526753653581080342170440070041444036999060620244113162142026706659814320006281319307590989529609584489765523538060605906643520397501088261161057489036035495926218707466334849330062895731371030622673217583249968410095234838280062973899067051705327936454698176051223300425382743605971100750125353577299211124316634511020496822736956635910618700094223093800997167520765080833881760946000203171960086745031585626938520440839096609754800426672160625268454400024712759001399391974274987401644837600085398060942003105427691759165268316416422755342621922961211216834742603935204676075726065563573486427707417346878394907689437403762692206010864758982291027230717621567583429938018782100054304010137021990595607550583706563758902718725273672513871591695624288791057389462131845354568850839942598374894488204878594950003391503330555937553542701376178835574233998674679832038442042687746736045151810062332080194310328547345588875530457028034684067955116540823659662627587432678579794981169007465651502935809712887685857134836872716951113818541865672079739042142946251953127625529127062636051620403386930993195654379248976844596535917581273804281268527796760250788695622393095585745767530704381532061810868657165330106299343577732338490208084310392413129721551997863114883829113362896033836348415665723851312620644269147483581436462637021253823053739680916347525649952537426074996063584811606056529489946745645370842295387064721335540522295052123174357444700065218903241875005281364502172589926400361773394499223685860681181660168173389754823238439864573355649735501036833916562476728426752814652276145924499796468801649893038661413701021723542199915104946194038478388240080986470648776600522532689828133838794045456802929075641332153607604359712005479314600456908120276890590603033439015747259570549451203879507313018214949811840753712392107213058276778225898534519125361584496040623340865223765074320276933025541607498707766471930645428534507092539000799716129770456173567162670634562024658505440868081402504722647525243456562447316709201061758214553272218248576765414996668721889976263512807274604420558968406597640128885202248370283733760823216588212968700848509191964192150570859109759821503641488955237019178970806803399999582476711492088514766267265986416833055145609886518742159257521310504347274680023063725278077369413435019572727956739800326766053435527930461451504486778731012647345185970275380666132047274583915310059368328883004545752728544926810411269704813842038381494254316528409574046994929692012997579232338789880505869437058459293601698470716752969994402526808032263379241816413731936375273740394349662488801204138573516723578191660977797236115965179222928387981603749417502190165727297958783274622820763478924168778171614387303190856079591153705178710499871802426441817917138316059824880227423333341033980200890813640094401212809254525768921511193956703094640588955556402839140042289262203210417555696581851515591903784135593638611920152840259304077491921428013710628217967731221107673665605264277051835330513601832591973366184345700700835418264146960073009106555730248160110826480736776863958376590589538766670512853860406231470933203511689778107391910956569470309205510554652806470273439245458874579207078916700137015611277070871207007274098410135764751039425403720449939538023480329782319324587643410215763650518325673123744501405341455819172755897739459364408410984682600355859848466109271107153575426652248520084648056863861845051820349721383314188961211961492168690260593378922274377806852793060708081167475950749853111834363133136227238946734128453649888681831675990117238143837639555334607401985960553990350341954185923440403095944596961336984604649545345270141882172787341507104046432136181285593459950945659074113003086911307074561084139016707589690321114646464973175238724132848975171820331780559295362588039786861714975186455121748920912650448257973374165045421881329876575475453497561485555718812024066829092005789902400612692132069377962694909124459558401437721200762255955391975450662656030585698577603468450540781122241909477121141277475487022550555991232086620592330484696107504748212042717024984511128514489572337103290497463053038297017270213536117785575209241005892337374447981420382631507627473020738146287721471828402572774912968182156919163235789313606866181288797605964230372286562196441885248747051641889752951498265073338040067917966423012905447158671454563376483476749086132203893597641438171159940596440833015935727218097999182491045576386105461297954891648529495006700933025479833812209541839516079299355016177170290186545646378795238592809354044119320124783732065211507478645164074591996377071295519182881268887164010110121740175609643377504920370408483585403156812688264331877716008451684630761824977882460172101709586380077307055771689763061878695333976490555741600452480713998630306532365944227765153727052679846158967344020910647616592545589704289990048386290687889870782038190706906423200051962908402722481927872123663347400143907800402901331312261630167565213094783826911792590848714582048892211911977102556438161955222502468386217804432061857111469012454605258352627072207452487734127418202944832459587047274929389909038537360943803391538402947740834395751362248922729454802003091741560425101815974258846254810114208988067632237171520011099220192218071954610544497563908505737343048821477180485033234049718291402305488585862078216098332935020654301135883101520192697306928219966732877977680710893809779344427352176333083845284119739475406312449444192575451649637114092634058176589888635957473712871952914554271095285233214086360582507270932866216275630271730019384707870747579414425663225753901317545396097565404198083307630031715707126760311074001430702038648469826950584734961874114290507424041402199316555753857996116642358276350704783286993855921641123239788993397633895244252855843976151755930750275954184441106692459009013040773601413556887082994340452398055934505831930527540057405643938241112933175509978457715448499211983927651693784065649069385650480953775613013165876685253015633695490707919256809599210583980381443258460974780382413319290435500545658456465259810197526161518658062781294642760153560044493465506719945776433268097238851011031560567502199567030353965790137267751315038861876218226590390720488513880151296356367375416212727179370941137478194386743847032788378985843677560012512848415077759064136218412038812133274390530972895264610112723014501837033790978576302182528171072216052105112167882700713861709431351873831312358017387268299666981615621187993840811342840830306549940806140258228873625065848302857079023226929011114561897962253411549058129222350958419753013243230925093661303053943086380345315851419008067813878644371400574170352045429024274328252311773620590884101222710185495930619613145127819977925916475184331344735697115040920340653204891315928676694924086143925312059073082688991871070191585107130366980317148529663298202341000314379198378581624709196879584440047639
1327977883153630750253802408334840376586662559883560082339583833838479581174923081361364759922823557337207033246998902626121453574513503722585640639059869100679908541254093649553810649501938456980290145076651160681163303714373259162233015519315504448267323283609437003175814793679897804885642889124653639439695549166287293605038775308835154661810546716552325292936458563120296414577423656271463390594198407996466791461625240054039629257931340461566360406832010775674649951534089103594271619960537011074278366615528113454495915601544463438979704698667997982970408132248843749468336019497145380790476980089830757301009525813899611689704454968892539639261166674752200298848729866149054425694563386881875882450384083685726056604366105774285215419315303855814293282784365937910602131537926247923509149838912855148174644528243315638400269024283781331370327209908964543947430583230437366006664782185041028602812226370063188118874779810219771317203134111407738416089116022094168786842326084193197247745213321669353442225155190813529389760300069901801565753319734314624142484198969248742590449995236326892196404921523097964928462928604584053874277006017634538627103686931789993404311879071899959718009830282764304267473890058702054614237918554820369321884704071662660464389795293153567637637227767353732684623744628559393516617754571829107745527739473331274055653831039530167696033806954575621296799068625464972669604502498186404717783382806314562754694232287220748883253045573744535323061402447968462378046456243866874183516434123919718523700340745693868270566735588610342487600973091515455948188649199460296046067549842439485893281786010793505468153161707009248805908485864758189918412690420609774499816191244942873262102356273062899266300152524697655124375343027635902747657416197636889313770791664424099497901297478200769888012521535050692381827366819454197498390331453961137226305703548821820119428521674633959384269354656044138171460985873797513936356698884712133519751736547116130790667038472214864621958034882609625460068828721456526340235268536522851754856023146641959104283580773055404220075335998958226586646423333171736386089750327264363531505907730280921932361804770287325465317435760947954463392682416447276956557741468271947274682693635345283885173420883487400710399250336067859498281295764467882565693680955892847224896317213543790300437853882465335141026379366874119775091773863840792133019072949614880973990588846764846655173818470420849471975043941060967316832646436973548183417573736967026252380126389186917751267646923110636122251891399938522789640577898786225075109538994356922773513337430862556554307848460511709399035306457338988111647983534863157813762899040108159272107735104584353360739846467027495198784871970609748673422470853839487623642693277601052972561448280166900457963386933407873808974954205674325937981918428691711019356489496647663046154847872113642365157231938836272158650467167926904239775351225373579651462653925620500348644269782329326981982053207989739332314710636540774970450980863774690178251429783613600249415654125875374459777743001116442319208450469583668218432224254063989438511325490233583878703968927159401548749228639936832750674454688851399994867540209457541727385780260232381328793699342870621699608884995956514780902835684292955628112789214237370390566850788116914185541977970574321936775897083161179439724850055002107108923609680838892633792086206730491981281406782696945945610643897601823293168860199470562158459757803340966967466621260070870468066420419131299126908926590607398657987148350701821897671501049319872364494235823303955936336906636413318959014772702688709128183164862194705834799462775013053859914733703170231039953766527615813723721103067890412319487375429631228037837494997231074086177223427617494382129556943721185975085797022262076055253053568747399154600283872158997323725378895122992883307610988440116380908882572777944348655560362105952384763797214443403637491161871758751401547485300495841659472523355631810853886203470375782827741337413371542964671887067331174747167912917139349323461669562335713084181059354136227052418358833873060946100317966708418309719635760020795372002049583645540041705911815714512100145680466013706852492868158834195748747573846502622626374565666490598926586447724761443540687314596012169223982019756475338551534341036471672827570308837054893350260802115322502597725521614558500539533694942041763636032215507247018077307176921599777085165998744907203093683748828768707250845096052321084872500144188797244310793183578593953734827356400614498343893806505551421794522320817503239999854932756545578083262232869693430731322375207021046303539781987948831707038441236294726054459888244154151351747450643437336647424094468643154073185506221353012132622043729565271046104070010570158889974380579033226039142664647967243270337481825157320077474580397452295847254004491408088706437532187697646676099420271283243018712935077397778025022947205314981931431755872418775398842958072364798790290490813568194613005767839211481745500785762871147943454446759089494818615809248653535587146659745258497350999002055789098508930808242711686364576846002089434297289305897050305625891527514035464348538751115283815926945671791750554917360131081484412794502492643482759411628578944117077896848567459025803742446519568230730567715817130783997303402354467901893492773390192071386522486009431604165830877933251442111048940600268431617064820667391574245046881991545450558866237984265957570573345785065006842257308698019373348761281358037778200912296759438465449132261907159020506803137149801826529290697039401096910798474717914870050292354906816232738495068665614802718625422165800842440279029899955964282031047236892733354116173855254728673511326128570584129318918393453959605090528042642615959540741400587146989259042114086805712425312605187611888745911738644151354253610707795736494849727137883717163705206221444715981634617587967451601100953042692390212986026167661532412360905732608898680037599686661979405597111836473092559027025739501860752550825910470765240077962086036678392508946781102082613545423692240894769417203987191526930878616238606356369231872080437750225970739061583431074862966984483183529387001016361126292575648700851119929564469136181354005360583673647355583996266145092095088611237524396290763255124339939773431530944987393211569138819377447807717756747116950644987353899324846803327560548188330043320804092299950480277018354014673135693718347731000926765865544956021328606311653183075242809240912961439410800381755869308463402348886151274771376793694118089144015795037660609777682306318763723617670439070579154899289746951381914637740878340591242553869862080478587446241852416743870110280167888120853072677524977227401521028147064192160931526773451513352905744421292862453919166701487863517764615029977478187495971776442110539657538007644067389743974804514314185475227544849120392484597398316269781712766267770472226436392698074840181245439691563790346327133377914023545690495833722616998292475934452861403370364817016417856565364497871478424765670288305902676903569950826468390226301669727532104823616976156772908224662672530931333574280350574250548875583597492332352801064061657385996347410598302824709026801186071480777926432680336415136882919183099407131412597611095177139566306485018467939106092217253519167326369150409295871452374368731190805973361622188185899700741761248635094607039089125990945936863180092449854319645998582089357924569219671957352420269371804599467693537718082870389756773489248875786600728795555155088937871052288327428564897681581462197364240947085321946899426867403644680036250712445456645250885573056468001949320654701278597618732087844340609087440412714676089210805515478887655560318233415812183908874689310470574765744943549609249372205882325117803860431092114183561859000599680048063616677679125831119905736427145273122704674992592933844707259305958132624090313827300050546508338460541081476227158753648455974025991430013830372902599501740594513619039899006623735632085003800847114300631202051782595423394075591498282518915802615262642874379460864951231711100162729385179860565439373293430608211018381423337673012499380816531891228955960994799404753825495779625615466413551458696771281756681001135282643533274853184680472429294225523783628817960586375537467092636162826302546960200238089760963079472863383210607932291347372729515596087314876513355292352897795620633245669790116546983145230401828874922873992261987112504112525237684186544406339257026170492116224229229144181555075087023220241461283138677585465127560647476110269930434587043329072085269862459361818597196984809387151260271980848045852442347654012976029418146752717942096410165904462597481723250228154165280476976237376775782307577428740879970270227667207355686830001915933263541722045777653681008080594375816011889482963336298946623543959750938427215604340639008253527089840961069658771334027568616514202495134057838011571730153636528700137074476211492839028428401660629385826545103205108907355379964473808696316564962757233856895279215857783975345077167555204660860795608749995678780261387519339047018114888943927658204686783471061167631285546272205302260545479323534624845957225844322767588923378248629451298862539490198690386086538719459072318906026208779134958464561134076685204776952286290897993310108311205648632699055816184394273133202882875721282640261805907021165343573320948986670497823608641371937409559242613143290054931012081870658416218164852913989216631696152871542399488934327074435454459590422763986512940446190173501125880896011251565317091078948134784975959158577899967447740106564385199694003674009095095074084928270248165523771563204736698943373424373796425809020239948573859064689722710893341039001517703047601988656985054863072391529880612534355075611131743980115249683589717040024727627617123185416118507694954213423031255481666793559598263221335575033058267628255037733195323550015363531627586343557733540492738664881456309550928253948823652151211701623692496414171651664049989026902613632

正解:

13830612

错解:

5430205

PS:我好像发现正解和错解的和为$p$