Wprowadzimy podział na dowolnie duże liczby całkowite.

To jest golf golfowy .

Zadanie polega na napisaniu programu lub funkcji, która implementuje na nich dowolne liczby całkowite precyzji i dzielenie.

Pamiętaj, że wiele rzeczy, które mogą sprawić, że będzie to bardzo łatwe, jest niedozwolonych, przeczytaj tę specyfikację .

Wejście

Otrzymasz 2 rzeczy jako dane wejściowe:

1. ciąg 10 cyfr, nazwij to n .
2. inny ciąg 10 cyfr podstawowych, nazwij to m

Załóżmy, żen>m>0 oznacza to , że nigdy nie będziesz proszony o podzielenie przez zero .

Wynik

Wyprowadzisz dwie liczby, Qa Rgdzie m * Q + R = n i 0 <= R <m

Dane techniczne

• Przesłanie powinno działać dla dowolnie dużych liczb całkowitych (ograniczonych dostępną pamięcią).

• Nie możesz używać bibliotek zewnętrznych. Jeśli potrzebujesz zewnętrznej biblioteki dla we / wy, możesz potraktować ją jako wbudowaną. (patrząc na rzeczy takie jak iostream itp.).

• Jeśli Twój język ma wbudowaną funkcję, która trywializuje to, nie możesz go używać. Obejmuje to (ale nie wyłącznie) typy wbudowane, które mogą obsługiwać liczby całkowite o dowolnej precyzji.

• Jeśli język z jakiegoś powodu domyślnie używa liczb całkowitych o dowolnej precyzji, tej funkcji nie można użyć do przedstawienia liczb całkowitych, które zwykle nie mogą być przechowywane w 64 bitach.

• Wejście i wyjście MUSZĄ znajdować się w bazie 10 . Nie ma znaczenia, w jaki sposób przechowujesz liczby w pamięci lub jak wykonujesz na nich arytmetykę, ale we / wy będzie bazą 10.

• Masz 15 sekund na wyprowadzenie wyniku. Ma to na celu zakazanie iterowanego odejmowania.

• Celem jest tutaj implementacja liczb całkowitych o dowolnej precyzji. Jeśli z jakiegoś powodu jesteś w stanie zastosować się do specyfikacji wyzwania i z powodzeniem zrobić to bez ich implementacji, to chyba dobrze dla ciebie, brzmi poprawnie.

Przypadki testowe

1. W tym przypadku dane wejściowe wynoszą 39! i 30!

Wejście

n = 20397882081197443358640281739902897356800000000 
m = 265252859812191058636308480000000

Wynik

Q = 76899763100160
R = 0

2. njest sumą wszystkich silni do 50, plus 1. mto połączone liczby do 20.

Wejście

n = 31035053229546199656252032972759319953190362094566672920420940313
m = 1234567891011121314151617181920

wynik

q = 25138393324103249083146424239449429
r = 62459510197626865203087816633

3. njest 205! + 200 !. mto ile łez PeterTaylor sprawił, że wylałem, rozrywając rzeczy, które umieszczam w piaskownicy.

Wejście

n = 271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000
m = 247

Wynik

q = 1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000
r = 0;

Prawdopodobnie w pewnym momencie dodam więcej przypadków testowych.

Związane z

Brzmi powiązane, ale tak naprawdę nie

Python 2, 427 bajtów

b=S=lambda l:sorted(l)[::-1]
A=lambda a,b,o=0:A(a^b,{n+1for n in[b&a,b-a][o]},o)if b else a
M=lambda a,*b:reduce(A,({n+m for n in a}for m in b))
def D(a,b):
 q=a-a
 while b<=S(a):n=max(a)-b[0];n-=S(M(b,n))>S(a);q|={n};a=A(a,M(b,n),1)
 return q,a
exec"a=b;b=[]\nfor d in raw_input():b=A(M(b,3,1),{i for i in range(4)if int(d)>>i&1})\n"*2
for n in D(a,S(b)):
 s=''
 while n:n,d=D(n,[3,1]);s=`sum(2**i for i in d)`+s
 print s or 0

Odczytuje dane wejściowe przez STDIN, każdą liczbę w osobnej linii, i drukuje wynik do STDOUT.

Wyjaśnienie

Zamiast reprezentować liczby całkowite jako tablice cyfr, reprezentujemy każdą liczbę całkowitą jako zestaw bitów „on” w jej reprezentacji binarnej. Oznacza to, że liczba całkowita n jest reprezentowana jako zbiór wskaźników bitów, które są równe 1 w binarnej reprezentacji n . Na przykład liczba 10, 1010 w postaci binarnej jest reprezentowana jako zbiór {1, 3}. Ta reprezentacja pozwala nam zwięźle wyrażać niektóre operacje arytmetyczne, używając operacji zestawu Pythona.

Aby dodać dwa zbiory, (rekurencyjnie) bierzemy sumę ich symetrycznej różnicy, a zbiór kolejnych liczb całkowitych do ich przecięcia (co odpowiada zbiorowemu przeniesieniu, a zatem ostatecznie staje się pustym zbiorem, w którym to momencie mamy końcową sumę .) Podobnie, aby odjąć dwa zbiory, (rekurencyjnie) bierzemy różnicę ich symetrycznej różnicy, a zbiór kolejnych liczb całkowitych do ich (zbioru) różnicy (która odpowiada pożyczce zbiorowej, a zatem ostatecznie staje się zbiorem pustym, w w którym punkcie mamy ostateczną różnicę). Podobieństwo tych dwóch operacji pozwala nam zaimplementować je jako pojedynczą funkcję ( A).

Mnożenie ( M) jest po prostu rozproszonym dodatkiem: biorąc pod uwagę dwa zestawy A i B , bierzemy sumę, jak opisano powyżej, wszystkich zbiorów { A + b | b ∈ B } (gdzie A + b jest zbiorem { a + b | a ∈ A }).

Porównanie liczb całkowitych staje się porównaniem leksykograficznym dwóch zbiorów, posortowanych w porządku malejącym.

Aby podzielić ( D) dwa zestawy, A i B , zaczynamy od pustego zestawu jako ilorazu i wielokrotnie znajdujemy największą liczbę całkowitą n , tak że B + n jest mniejsze lub równe A (co jest po prostu różnicą między maksimami z A i B , prawdopodobnie minus-1), dodaj n jako element do ilorazu i odejmij B + n od A , jak opisano powyżej, aż A stanie się mniejsze niż B , tj., aż stanie się resztą.

Oczywiście nie ma bezpłatnego lunchu. Płacimy podatek, przeliczając z dziesiętnego na dziesiętny. W rzeczywistości konwersja na dziesiętne zajmuje najwięcej czasu. Konwersję wykonujemy „w zwykły sposób”, używając tylko powyższych operacji, zamiast zwykłej arytmetyki.

Java 8, 485 bajtów

Można zmniejszyć o kolejne 5 bajtów nazywając funkcję dzamiast dividelub o kolejne 16 bajtów, jeśli nie licząc definicji klasy.

public class G{int l(String a){return a.length();}String s(String n,String m){while(l(n)>l(m))m=0+m;String a="";for(int c=1,i=l(n);i>0;c=c/10){c=n.charAt(--i)+c-m.charAt(i)+9;a=c%10+a;}return e(a);}String e(String a){return a.replaceAll("^0+(?=[0-9])","");}String divide(String n,String m){String q="",p=q,y;for(int b=0,i=0;b<=l(n);i--){y=n.substring(0,b);if(l(y)==l(p)&&p.compareTo(y)<=0||l(y)>l(p)){y=s(y,p);n=y+n.substring(b);q+=i;b=l(y)+1;i=10;p=m+0;}p=s(p,m);}return e(q)+","+n;}}

Można użyć w następujący sposób:

public static void main(String[] args) {
    G devision = new G();
    System.out.println(devision.divide("20397882081197443358640281739902897356800000000",
            "265252859812191058636308480000000"));
    System.out.println(devision.divide("31035053229546199656252032972759319953190362094566672920420940313",
            "1234567891011121314151617181920"));
    System.out.println(devision.divide(
            "271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000",
            "247"));
}

wydajność

76899763100160,0
25138393324103249083146424239449429,62459510197626865203087816633
1100573825740813795225181252819477770473619155158611722708681386445423816849801159141424129060075102231232666057768175183676764503262931271346408394876267875141461722640873365274628650676808557279259873162169126398101692109801549256156915750794061370041981513180387019893765753438422927286098434193260562682052606153857091520795991080960000000000000000000000000000000000000000000000000,0

Nie golfowany:

public class ArbitraryPrecisionDivision {

    /**
     * Length of String
     */
    int l(String a) {
        return a.length();
    }

    /**
     * substract m of n; n >= m
     */
    String s(String n, String m) {
        while (l(n) > l(m))
            m = 0 + m;
        String a = "";
        for (int c = 1, i = l(n); i > 0; c = c / 10) {
            c = n.charAt(--i) + c - m.charAt(i) + 9;
            a = c % 10 + a;
        }
        return e(a);
    }

    /**
     * trim all leading 0s
     */
    String e(String a) {
        return a.replaceAll("^0+(?=[0-9])", "");
    }

    /**
     * divide n by m returning n/m,n%m; m may not start with a 0!
     */
    String divide(String n, String m) {
        // q stores the quotient, p stores m*i, y are the b leading digits of n
        String q = "", p = q, y;
        for (int b = 0, i = 0; b <= l(n); i--) {
            y = n.substring(0, b);
            if (l(y) == l(p) && p.compareTo(y) <= 0 || l(y) > l(p)) {
                y = s(y, p);
                n = y + n.substring(b);
                q += i;
                b = l(y) + 1;
                i = 10;
                p = m + 0;
            }
            p = s(p, m);
        }
        return e(q) + "," + n;
    }

    public static void main(String[] args) {
        ArbitraryPrecisionDivision division = new ArbitraryPrecisionDivision();
        System.out.println(division.divide("20397882081197443358640281739902897356800000000",
                "265252859812191058636308480000000"));
        System.out.println(division.divide("31035053229546199656252032972759319953190362094566672920420940313",
                "1234567891011121314151617181920"));
        System.out.println(division.divide(
                "271841734957981007420619769446411009306983931324177095509044302452019682761900886307931759877838550251114468516268739270368160832305944024022562873534438165159941045492295721222833276717171713647977188671055774220331117951120982666270758190446133158400369433755555593913760141099290463039666313245735358982466993720002701605636609796997120000000000000000000000000000000000000000000000000",
                "247"));
    }
}

Poświęciłem trochę prędkości, nie dokonując wstępnego obliczenia tablicy z mczasami od 1 do 9 i zaczynając od b=0zamiast b=l(m), ale zaoszczędziłem na tym wiele bajtów. Jeśli interesuje Cię dowolne dodawanie precyzji, zobacz poprzednią wersję .

Myślę, że nie będzie to najkrótsze rozwiązanie, ale może to dobry początek.

Mathematica, 251 bajtów

r=Reverse;f=FoldPairList;s={0}~Join~#&;
p[a_,b_]:={First@#,#[[2,1,-1,2]]}/.{Longest[0..],x__}:>{x}&@Reap@f[Sow@{Length@#-1,Last@#}&@NestWhileList[r@f[{#~Mod~10,⌊#/10⌋}&[#+Subtract@@#2]&,0,r@Thread@{#,s@b}]&,Rest@#~Join~{#2},Order[#,s@b]<=0&]&,0s@b,s@a]

Wyjaśnienie

Arytmetyka liczb dziesiętnych może być łatwo zaimplementowana przez FoldPairList. Na przykład,

times[lint_,m_]:=Reverse@FoldPairList[{#~Mod~10,⌊#/10⌋}&[m #2+#]&,0,Reverse@lint]

po prostu naśladuje proces ręcznego mnożenia.

times[{1,2,3,4,5},8]
(* {9,8,7,6,0} *)

Przypadek testowy

p[{1,2,3,4,5,6,7,8,9},{5,4,3,2,1}] 
(* {{2,2,7,2},{3,9,4,7,7}} *)

środki 123456789 / 54321= 2272...39477.