分圆多项式
问题在于精度貌似出了一些奇怪的问题。。。
【输出也写的有问题QAQ】
完全不会处理了 加上全网没有题解T^T
挖个坑以后补。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 20021225
#define ll long long
#define mxn 10100
#define pa pair<int,int>
#define mp make_pair
#define db long double
using namespace std;int d[mxn][mxn];int m[mxn];
bool vis[mxn];
// x -> n y -> powtemplate<typename T>
inline T labs( const T & x ){return x<0?-x:x;}template<typename T>
inline int sgn( const T & x ){return x<0?-1:(x?1:0);}inline int d_round( const db & x ){return (int)(sgn(x)*(labs(x)+0.50001));}const db pi=acos(-1.0);
struct complex
{db x,y;complex(){}complex(db _x,db _y){x=_x,y=_y;}
};
complex tmp[mxn],fin[mxn];
complex operator +(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator -(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator *(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y);}
int gcd(int x,int y)
{return y==0?x:gcd(y,x%y);
}
void calc(int n)
{if(vis[n]) return;vis[n]=1;for(int i=0;i<n;i++) tmp[i]=complex(0,0);tmp[0]=complex(1,0); int c=1;//printf("--------%d---------\n",n);for(int i=1;i<n;i++){if(gcd(i,n)!=1) continue;//printf("%d %d\n",i,n);db qaq=(db)i/(db)n*2.0*pi;// printf("%lf\n",qaq/pi);for(int j=c;j;j--){tmp[j] = tmp[j-1] - tmp[j] * complex(cos(qaq),sin(qaq));//if(i<10) printf("%lf ",tmp[j]);}tmp[0] = complex(0,0) - tmp[0] * complex(cos(qaq),sin(qaq));//if(i<10) printf("\n");c++;}m[n]=c;for(int i=c;~i;i--){d[n][i]=d_round(tmp[i].x);//printf("%lf ",tmp[i].x);}
}void get(int n)
{int f;for(int i=1;i<=n;i++){if(n%i==0){calc(i);f=0;for(int j=m[i];j>1;j--) {if(d[i][j]){if(!f) printf("("),f=1;if(d[i][j]<-1) printf("%dx^%d",d[i][j],j);else if(abs(d[i][j])==1){if(f==1) printf("x^%d",j);else if(d[i][j]==-1) printf("-x^%d",j);else printf("+x^%d",j);}else printf("+%dx^%d",d[i][j],j);f=2;}}if(d[i][1]){if(!f) printf("("),f=1;if(d[i][1]<-1) printf("%dx",d[i][1]);else if(abs(d[i][1])==1){if(f==1) printf("x");else if(d[i][1]==-1) printf("-x");else printf("+x");}else printf("+%dx",d[i][1]);}if(d[i][0]>0) printf("+%d)",d[i][0]);else printf("%d)",d[i][0]);}}printf("\n");//printf("%lf\n",cos(4.0/11.0*pi)+cos(6.0/11.0*pi));
}int n;
int main()
{vis[1]=vis[2]=1;m[1]=m[2]=2;d[1][1]=d[2][1]=1;d[1][0]=-1;d[2][0]=1;while(scanf("%d",&n)&&n)get(n);return 0;
}
