10951 - Polynomial GCD

[rage_true]

Someone who have gotten AC give me plz some test cases

[rage_true]

or look at my bad code(sorry for bad style):

Code: Select all

#include <stdio.h>
#include <memory.h>

#define FOR(i,n) for(i=0;i<(n);i++)
#define FORR(i,a,b) for(i=(a);i<=(b);i++)
#define set(x,f) memset(x,f,sizeof(x))

int n,i,j,nt,bf;
int a[103],b[103],c[103];
int r[1501];

void mod(int a[103],int (&b)[103])
{
	int i,j,k,rep=b[102]-a[102]+1;
	int bf[103];
	c[102]=101-(b[102]-a[102]);
	FOR(j,rep)
	{
		k=(r[b[ b[102] ]]*a[ a[102] ])%n;
		FORR(i,b[102],101)bf[i]=(b[i]*k)%n;
		FOR(i,101-b[102]+1)
			a[a[102]+i]=(a[a[102]+i]-bf[b[102]+i]+n*n)%n;
		a[102]++;
	}
}

bool empty(int a[103])
{
	int i;
	FORR(i,a[102],101)if(a[i]!=0)return false;
	return true;
}

void gcd(int (&a)[103],int (&b)[103])
{
	if(empty(a))memcpy(c,b,sizeof(b));
	else
	{
		if(a[102]>b[102])
		{
			mod(b,a);
			gcd(b,a);
		}else
		{
			mod(a,b);
			gcd(a,b);
		}
	}
}

void main()
{
	nt=0;
	while(scanf("%d",&n)==1 && n!=0)
	{
		FOR(i,n)FORR(j,i,n-1)if((i*j)%n==1){r[i]=j;r[j]=i;}
		printf("Case %d:",++nt);
		
		scanf("%d",&bf);a[102]=101-bf;
		FORR(i,a[102],101)scanf("%d",&a[i]);
		FORR(i,a[102],101)a[i]=(a[i]+n*n)%n;
		
		scanf("%d",&bf);b[102]=101-bf;
		FORR(i,b[102],101)scanf("%d",&b[i]);
		FORR(i,b[102],101)b[i]=(b[i]+n*n)%n;
		
		if(empty(a) && empty(b))
		{
			printf(" 0 0\n");
			continue;
		}
		if(empty(a) && !empty(b))
		{
			memcpy(c,b,sizeof(b));
			printf(" %d",101-c[102]);
			bf=r[ c[c[102]] ];
			FORR(i,c[102],101)c[i]=(c[i]*bf+n*n)%n;
			FORR(i,c[102],101)printf(" %d",c[i]);
			printf("\n");
			continue;
		}
		if(!empty(a) && empty(b))
		{
			memcpy(c,a,sizeof(a));
			printf(" %d",101-c[102]);
			bf=r[ c[c[102]] ];
			FORR(i,c[102],101)c[i]=(c[i]*bf+n*n)%n;
			FORR(i,c[102],101)printf(" %d",c[i]);
			printf("\n");
			continue;
		}
		gcd(a,b);
		
		printf(" %d",101-c[102]);
		bf=r[ c[c[102]] ];
		FORR(i,c[102],101)c[i]=(c[i]*bf+n*n)%n;
		FORR(i,c[102],101)printf(" %d",c[i]);
		printf("\n");
	}
}

[danielrocha]

I'm not sure this will be very helpful, but this is the input we used during the contest:

Code: Select all

3
3 2 2 1 1
4 1 0 2 2 2

3
3 2 2 1 1
2 1 2 1

3
4 1 0 2 2 2
2 1 2 1

100
10 1 2 3 4 5 6 7 8 9 10 11
10 1 2 3 4 5 6 7 8 9 10 11

100
5 10 0 0 0 0 0
5 15 0 0 0 0 0

1500
4 1 2 3 3 1
5 1 1 4 3 4 2

1500
4 2 4 5 5 2
5 1 1 4 3 4 2

1500
4 1 2 3 3 1
5 2 2 8 6 8 4

0

And the ouput from our AC algorithm:

Code: Select all

Case 1: 2 1 2 1
Case 2: 2 1 2 1
Case 3: 2 1 2 1
Case 4: 10 1 2 3 4 5 6 7 8 9 10 11
Case 5: 5 1 0 0 0 0 0
Case 6: 0 1
Case 7: 0 1
Case 8: 0 1

Hope it helps.

[rage_true]

Thanks for your help, but it seems to me, that answer for
case 6:
4 1 2 3 3 1
5 1 1 4 3 4 2
will be 3 1 1 2 1, but not 0 1.
I think 3 1 1 2 1 divide both 4 1 2 3 3 1 and 5 1 1 4 3 4 2 with no remainder.
Plz explain.

PS. I've just changed module of ring 1500 for prime number(53) for correctness of input data.

[LIBe]

I can't approach to this problem.

Plz someone help me...

[misof]

The basic idea is that Euclid's GCD algorithm works for polynomials, too. If both f(x) and g(x) are divisible by h(x), then f(x)-c(x).g(x) is divisible by h(x) for all c(x). Partially divide f by g to get c, subtract, continue.

[shanto86]

rage_true you are right. case 8 and case 6 will be, the answer you gave.

[Jan]

I think those cases are not correct. Since n is a prime number. Read the description again...

Each test case consists of three lines: the first line has n, which will be a prime number not more than 1500