10951 - Polynomial GCD
Moderator: Board moderators
10951 - Polynomial GCD
Someone who have gotten AC give me plz some test cases
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");
}
}
-
- 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:
And the ouput from our AC algorithm:
Hope it helps.
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
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
Daniel
UFRN HDD-1
Brasil
UFRN HDD-1
Brasil
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.
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
I can't approach to this problem.
Plz someone help me...
Plz someone help me...
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
HomePage