Page 1 of 1

### 10951 - Polynomial GCD

Posted: Sat Oct 29, 2005 8:25 pm
Someone who have gotten AC give me plz some test cases

Posted: Sat Oct 29, 2005 8:33 pm

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

Posted: 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.

Posted: 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.

### 10951 - Polynomial GCD

Posted: Mon Oct 31, 2005 8:14 am
I can't approach to this problem.

Plz someone help me...

Posted: 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.

Posted: Thu Jul 06, 2006 12:22 pm
rage_true you are right. case 8 and case 6 will be, the answer you gave.

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