10407 - Simple division

[Riyad]

i got my mistake for this problem . i did not consider a special case , as a result WA . i now got my mistake corrected .every one should consider the case when there r only 2 number in the sequence .
Bye
Riyad

[medv]

Help me, please! Why WA???

#include <stdio.h>
#include <math.h>

int gcd(int a,int b)
{
return (a == 0) ? b: gcd(b%a, a);
}
void main()
{
int a,b,res;
while(scanf("%d\n",&a),a > 0)
{
scanf("%d",&b); res = abs(a-b);
while (scanf("%d",&b),b>0)
{
res = gcd(res,abs(a-b));
a = b;
}
scanf("\n");
printf("%d\n",res);
}
}

[efr_shovo]

#include<iostream.h>
#include<math.h>

long data[1000],sub[1000],n,a,b;

long gcd(long x,long y )
{
if(y==0)
return x;
else
return gcd(y,(x%y));
}


void main()
{
while(1)
{
int i=0;
int k=0;

while(1)
{
cin>>n;
if(n==0)
break;
data[i++]=n;
}
if(data[0]==0||i==1||i>1000)
break;
int j=0;
for(j=0;j<i-1;j++)
{
sub[j]=labs(data[j]-data[j+1]);

}
a=sub[0];

for(k=1;k<j;k++)
{
b=sub[k];
a=gcd(a,b);
}
cout<<a;
for(j=0;j<i;j++)
{
data[j]=sub[j]=0;
}

}
}

[the LA-Z-BOy]

Code: Select all

cout<<a;

should be

Code: Select all

cout<<a<<endl;

[Jan]

Just try the following input:

Input:

Code: Select all

701 701 1059 1417 2312 0
0

Output:

Code: Select all

179

Find res and use a flag then calculate...

Hope it works...

[savage]

i got runtime error but why??somebody help me plz.................
here is da code...

#include <iostream>
#include <math.h>

using namespace std;

#define MAX 10000
#define MEX 100000
long a[MAX],b[MAX];
long prime[MEX];


long gcd(long c,long d);

int main()
{
long i,j,k;
int y,m,n,g,count;
prime[0]=0;
prime[1]=1;
for(m=2;m<=MEX;m++){
prime[m]=1;
}
for(m=2;m<=(MEX/2);m++){
for(n=m+m;n<=MEX;n+=m){
if(prime[n]==1){
prime[n]=0;
}
}
}
do{
i=0;
j=0;
count=0;
cin>>a;
if(*a==0)break;
while(*a){
i++;
cin>>a;
if(a==0)break;
b[j]=a-a[0];
j++;
count++;
}
for(k=0;k<count-1;k++){
j=2;
g=gcd(b[0],b[1]);
g=gcd(g,b[j]);
j++;
}
if(prime[g]==1){
cout<<g<<endl;
}else{
y=2;
while(y<=(g/2)){
if(g%y==0){
g/=y;
}else y+=2;
}
cout<<g<<endl;
}
}while(*a);
return 0;
}

long gcd(long c,long d){
if(c%d==0)return d;else return (d,c%d);
}

[kana]

why WA? can any one help?

Code: Select all

[Jan]

Check the samples...

Input:

Code: Select all

-666 169 0
-650 -164 0
-202 157 0
976 -632 0
762 531 0
615 234 0
-244 -722 0
-145 716 0
-783 482 0
721 421 0
-316 -721 0
0

Output:

Code: Select all

835
486
359
1608
231
381
478
861
1265
300
405

Hope these help.

[kana]

thanks jan !!!

[Taman]

I found the following type of test cases very helpful

Code: Select all

2 4 6 8 0
5 10 0
0

[theylosehope]

Hello guys,

I've got "10407 - Simple Division" AC using the description in Algorithmist. However, I don't fully understand it.

My algorithm:
- Add numbers to set "S".
- If size of S is two: print the difference between the two numbers.
- If size of S is > 2: Erase the first element, and find GCD among all the differences between the remaining numbers.

This works correctly. But can anybody explain it in simple words? How can I figure out that the largest dividend with same remainder among a set of numbers is the GCD among the differences except the first difference?

Thanks in advance.

[ojha]

Getting WA ... help please.

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector< int >v;

int GCD(int y, int x){
    if(!x) return 0;
    int store;
    while(y%x != 0)
    {
        store = y%x;
        y = x;
        x = store;
    }
    return x;
}

int main(){
    int input, pre, post, size, i;

    while((cin >> input) && input){
        v.push_back(input);

        while((cin >> input) && input){
            v.push_back(input);
        }

        sort(v.begin(), v.end());

        size = v.size(); //cout << size << endl;

        for(i = 1; i<size; i++){
            if(i == 1){

                pre = v[i] - v[0]; //cout << v[i] << endl;
            }
            else{
                post = v[i] - v[0];

                if(post >= pre)
                    pre = GCD(post, pre);
                else
                    pre = GCD(pre, post);
            }
        }

        cout << pre << endl;
        v.clear();
    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

2 2 4 0
0

Output should be 2

[raj]

I am facing problem the way of solving it...
Somebody solve by taking difference and then gcd all the numbers
Somebody take the minimum then subtract all the numbers with the minimum and then gcd the numbers

but i want to know how it solves the problem??? please someone explain me if you have time???

[richatibrewal]

I am facing difficulty in understanding its 3rd example:

Input : 14 -22 17 -31 -124 0
output: 3

14%3 = 2
whereas -22%3 = 1

Will someone plz explain this ?