Somehow I managed to solve [problem:901B] however I don't know why my solution works. My idea was to pick two random polynomials of degrees n and n-1 check how many steps it takes to find the gcd and return the polynomials if the answer is n. However doing the gcd over $\mathbb{Q}$ is a pain because of fractions. If you try to avoid them by multiplication by denominators things overflow pretty quickly. ↵
↵
So I decided to pick a prime and do gcds over the finite field $F_{p}$. The strange thing is with a medium sized prime like 1009 the algorithm took more steps over this field than over $\mathbb{Q}$. Then I tried using the prime 43 just to see what would happen, since it worked on the case where 1009 gave an incorrect answers and it. Surprisingly using 43 worked for all the cases. Anyone know of a special relationship between the number of steps the Euclidean algorithm for polynomials takes over $\mathbb{Q}$ and $F_{p}$ for a given prime $p$?↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
//polynomial division over the finite field F_p↵
vector<int> pdivFF(vector<int> p1, vector<int> p2, vector<int>& inv, int prime){↵
auto p1ff=modify(p1,prime), p2ff=modify(p2,prime);↵
int degp1=0, degp2=0;↵
int sz=p1.size();↵
for(int i=0; i<sz; i++){↵
if(p1ff[i]) degp1=i;↵
if(p2ff[i]) degp2=i;↵
}↵
int shift=degp1-degp2;↵
if(shift>1){↵
return vector<int>(sz,0);↵
}↵
auto rem=p1ff;↵
while(shift>=0){↵
int mult=rem[degp2+shift]*inv[p2ff[degp2]];↵
for(int i=degp2; i>=0; i--){↵
rem[i+shift]-=p2ff[i]*mult;↵
}↵
shift--;↵
}↵
return modify(rem, prime);↵
↵
}↵
↵
//count number of steps to find the gcd over F_p↵
int stepCtFF(vector<int> p1, vector<int> p2, vector<int>& inv, int prime){↵
int ans=0;↵
int sz=p1.size();↵
vector<int> noRem(sz, 0);↵
while(p2!=noRem){↵
auto rem=pdivFF(p1,p2, inv, prime);↵
p1=p2;↵
p2=rem;↵
ans++; ↵
}↵
return ans;↵
}↵
int main() {↵
↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int n;↵
cin>>n;↵
↵
vector<int> p1(n+1,0), p2(n+1,0);↵
p1[n]=1, p2[n-1]=1;↵
srand(time(0));↵
↵
default_random_engine gen;↵
uniform_int_distribution<int> dist(-1,1);↵
↵
//choose a prime and create the inverse table↵
int prime=41;↵
vector<int> inv(prime,0);↵
for(int i=1; i<prime; i++){↵
for(int j=1; j<prime; j++){↵
if(i*j%prime==1) inv[i]=j, inv[j]=i;↵
}↵
}↵
↵
//generate random polynomials until we have one that takes n steps to find the gcd over F_p↵
while(stepCtFF(p1,p2, inv, prime)!=n){↵
generate(p1.begin(), p1.begin()+n-1, [&dist, &gen](){return dist(gen);});↵
generate(p2.begin(), p2.begin()+n-2, [&dist, &gen](){return dist(gen);});↵
↵
}↵
↵
cout<<n<<endl;↵
for(int i:p1) cout<<i<<" ";↵
cout<<endl<<n-1<<endl;↵
for(int i=0; i<n; i++){↵
cout<<p2[i]<<" ";↵
}↵
↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
So I decided to pick a prime and do gcds over the finite field $F_{p}$. The strange thing is with a medium sized prime like 1009 the algorithm took more steps over this field than over $\mathbb{Q}$. Then I tried using the prime 43 just to see what would happen, since it worked on the case where 1009 gave an incorrect answer
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
//polynomial division over the finite field F_p↵
vector<int> pdivFF(vector<int> p1, vector<int> p2, vector<int>& inv, int prime){↵
auto p1ff=modify(p1,prime), p2ff=modify(p2,prime);↵
int degp1=0, degp2=0;↵
int sz=p1.size();↵
for(int i=0; i<sz; i++){↵
if(p1ff[i]) degp1=i;↵
if(p2ff[i]) degp2=i;↵
}↵
int shift=degp1-degp2;↵
if(shift>1){↵
return vector<int>(sz,0);↵
}↵
auto rem=p1ff;↵
while(shift>=0){↵
int mult=rem[degp2+shift]*inv[p2ff[degp2]];↵
for(int i=degp2; i>=0; i--){↵
rem[i+shift]-=p2ff[i]*mult;↵
}↵
shift--;↵
}↵
return modify(rem, prime);↵
↵
}↵
↵
//count number of steps to find the gcd over F_p↵
int stepCtFF(vector<int> p1, vector<int> p2, vector<int>& inv, int prime){↵
int ans=0;↵
int sz=p1.size();↵
vector<int> noRem(sz, 0);↵
while(p2!=noRem){↵
auto rem=pdivFF(p1,p2, inv, prime);↵
p1=p2;↵
p2=rem;↵
ans++; ↵
}↵
return ans;↵
}↵
int main() {↵
↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int n;↵
cin>>n;↵
↵
vector<int> p1(n+1,0), p2(n+1,0);↵
p1[n]=1, p2[n-1]=1;↵
srand(time(0));↵
↵
default_random_engine gen;↵
uniform_int_distribution<int> dist(-1,1);↵
↵
//choose a prime and create the inverse table↵
int prime=41;↵
vector<int> inv(prime,0);↵
for(int i=1; i<prime; i++){↵
for(int j=1; j<prime; j++){↵
if(i*j%prime==1) inv[i]=j, inv[j]=i;↵
}↵
}↵
↵
//generate random polynomials until we have one that takes n steps to find the gcd over F_p↵
while(stepCtFF(p1,p2, inv, prime)!=n){↵
generate(p1.begin(), p1.begin()+n-1, [&dist, &gen](){return dist(gen);});↵
generate(p2.begin(), p2.begin()+n-2, [&dist, &gen](){return dist(gen);});↵
↵
}↵
↵
cout<<n<<endl;↵
for(int i:p1) cout<<i<<" ";↵
cout<<endl<<n-1<<endl;↵
for(int i=0; i<n; i++){↵
cout<<p2[i]<<" ";↵
}↵
↵
↵
return 0;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
