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.