dzielenie duzych liczb

Odpowiedz Nowy wątek
2006-12-16 21:10
0

Napisałem program na dzielenie dużych liczb.

Dla zadanej pary liczb całkowitych a oraz b takich, że 1 <= b <= a <= 101000 należy odpowiedzieć na pytanie czy b jest dzielnikiem a, tzn. czy istnieje taka liczba c, że a = b * c.
Wejście

W pierwszej linii na wejściu podana została liczba zestawów testowych t <= 100. W kolejnych t liniach podane zostały pary liczb a b.
Wyjście

Dla każdego testu (pary liczb) należy wydrukować odpowiedź TAK lub NIE, w zależności od tego czy liczba b jest dzielnikiem liczby a czy nie jest.
Zestawy testowe

Dane wejściowe składają się z trzech zestawów testowych:

* pierwszy zestaw (za 5 pkt) zawiera liczby o wartościach z zakresu od 0 do 10^12,
* drugi zestaw (za 5 pkt) zawiera liczby o wartościach z zakresu od 0 do 10^100 o ilorazie nie przekraczającym 10000,
* trzeci zestaw (za 10 pkt) zawiera dowolne liczby z zakresu od 0 do 10^1000.

Przykład 1

Wejście:
4
737107165 138238716
895029855 829118347
877731309 137943
129577540 15020

Wyjście:
NIE
NIE
TAK
TAK

Przykład 2

Wejście:
4
3879851632967642997066477 186142673840800049769398
6826558408855795317681463 16529197115873596410851
413520334553845421371296 49135020740713571931
2485051131518365473435750 523168659267024310197

Wyjście:
NIE
TAK
TAK
TAK

Przykład 3

Wejście:
4
9740953732011264571090128203650791 947843766717637397084837304497637
62219940366834189343034718959652736 63415782292
21529935136031251449403318966831624 16283613240499194557170790487795798
96265206867283215696265189471683216 22826502544

Wyjście:
NIE
TAK
NIE
TAK

Program testy przechodzi mi bezblednie, ale jak wysyłam na strone www.spoj.pl/PP06MM to system pokazuje mi, że mój program przeszedł tylko 2. test. Moglibyście pomóc w znalezieniu błędu w moim programie ?

#include <stdio.h>
#include <string.h>

void reverse(char a[],int len)
        {
        int k,l,c;
        for(k = 0, l = len-1; k<l;k++,l--)
                {
                c = a[k];
                a[k] = a[l];
                a[l] = c;
                }
        }    

void odejmowanie(char a[],char b[],int lena,int lenb,int pozycja)
        {
        int z=0,p=0,i,j,k;
        for(i=pozycja,j=0;j<lenb;i++,j++)
                {
                k=(int)(a[i])-(int)(b[j])+p;
                if(k<0)
                        {
                        p=-1;
                        k=k+10;
                        }
                else
                        p=0;
                a[i]=(char)(k+48);
                }
        if(p==-1)
                a[i]=(char)((int)(a[i])-1);
        }

void spr1(char a[],char b[],int lena,int lenb,int &pozycja, int &ok)
        {
        int i,l1p,l2p;
        for(i=lena;i>pozycja;i--,lenb--)
                {
                l1p=(int)(a[i-1])-48;
                l2p=(int)(b[lenb-1])-48;
                if(l1p<l2p)
                        {
                        pozycja--;
                        if(pozycja<0) ok=2;
                        break;
                        }
                else if(l1p>l2p)
                        break;
                }
        }

void spr2(char a[],int &len)
        {
        int i;
        for(i=len-1;a[i]=='0';i--)
        len--;
        }

int spr3(char a[], int len)
        {
        int z=0,i;
        for(i=0;i<len;i++)
                if(a[i]!='0')
                        z=1;
        if (z==0)
                return 1;
        else
                return 0;
        }

int main()
        {
        int t,i;
        scanf("%d",&t);
        for(i=0;i<t;i++)
                {
                char a[10000],b[10000];
                int l1Len,l2Len,ok=0,k=0;
                scanf("%s %s",a,b);
                l1Len=strlen(a);
                l2Len=strlen(b);
                if(l2Len==1 && b[0]=='0')
                        ok=2;
                reverse(a,l1Len);
                reverse(b,l2Len);
                while(ok==0)
                        {
                        k=l1Len-l2Len;
                        spr1(a,b,l1Len,l2Len,k,ok);
                        if(ok!=0) break;
                        odejmowanie(a,b,l1Len,l2Len,k);
                        spr2(a,l1Len);
                        ok=spr3(a,l1Len);
                        }
                if(ok==1) printf("%s \n","TAK");
                else printf("%s \n","NIE");
                }
        return 0;
        }

Pierwszy test zawiera liczby z zakresu typu doubla wiec moglbym dac warunek ze jesli liczba jest mniejsz niz 10^12 to wykonuje normalne dzielenie na doublach, ale to nie o to chodzi.

Pozostało 580 znaków

2006-12-17 12:21
MKF
0

Czy nie uważasz, że pytanie o pomoc w zadaniu konkursowym nie wypada porządnemu uczestnikowi?

Pozostało 580 znaków

2006-12-17 22:13
0

Po pierwsze na stronie spoj.pl/PP06MM piszemy programy nie na konkursy, tylko na zajecie z praktyki programowanie, na Polibude Gd. Wzwiązku, że mam problem z tym zadaniem, proszę więc o pomoc. To nie jest żadne zadanie konkursowe, tylko normalne zajecia na uczelni.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0