største felles divisor (xcy, z)

[smslca]

kan vi finne verdien av gcd (xcy, z) lett og veldig fort bruke en datamaskin. hvor 1. "C" representerer "kombinasjonene" brukt i "permutasjoner og kombinasjoner '. 2. x er veldig veldig mange (ex: kan være på 100 eller 1000 numeriske siffer) 3. y er også stor å ha 2-5 siffer mindre enn x. 4. z er også stor å ha samme antall siffer som x.

 

[Klen]

Jeg håper jeg får spørsmålet rett, men ja, kan du få en rask og riktig svar for å finne GCD av xCy og z. Skriv et program, fortrinnsvis i C / C + + (helst bare fordi jeg liker det: D). I koden, lage en funksjon for xCy, for eksempel: int xCy (int x, int y). Returnere verdien i en variabel, int combi, (du kan selvsagt bruke flyte også) Så definerer GCD funksjon. Eks: int GCD (combi, int z); Alternativt kan du også ringe xCy () fra GCD () direkte som en parameter.

 

[eyalhoc]

GCD er trivielle: int GCD (int a, int b) {while (1) {a = a% b; if (a == 0) return b, b = b% a; if (b == 0) returnere en ;}} Ditt problem er at C + + gjør matematiske beregninger på 32 eller 64 bit data. Det du trenger er et stort antall bibliotek for å støtte 1000 sifrede nummer. Jeg anbefaler: https://mattmccutchen.net/bigint/