## 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

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

### 10951 - Polynomial GCD

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
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
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:
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
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

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
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
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