10951 - Polynomial GCD

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm

10951 - Polynomial GCD

Post by rage_true » Sat Oct 29, 2005 8:25 pm

Someone who have gotten AC give me plz some test cases

rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm

Post by rage_true » Sat Oct 29, 2005 8:33 pm

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");
	}
}

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Sat Oct 29, 2005 9:07 pm

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.
Daniel
UFRN HDD-1
Brasil

rage_true
New poster
Posts: 8
Joined: Mon Sep 13, 2004 5:25 pm

Post by rage_true » Sun Oct 30, 2005 4:32 pm

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
New poster
Posts: 6
Joined: Sat Oct 29, 2005 11:56 pm

10951 - Polynomial GCD

Post by LIBe » Mon Oct 31, 2005 8:14 am

I can't approach to this problem.

Plz someone help me...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Oct 31, 2005 9:04 am

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Thu Jul 06, 2006 12:22 pm

rage_true you are right. case 8 and case 6 will be, the answer you gave.
Self judging is the best judging!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon May 14, 2007 10:32 pm

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
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 109 (10900-10999)”