题目链接:http://poj.org/problem?id=1707
题意:给出n
在M为正整数且尽量小的前提下,使得n的系数均为整数。
思路:
i64 Gcd(i64 x,i64 y) { if(y==0) return x; return Gcd(y,x%y); } i64 Lcm(i64 x,i64 y) { x=x/Gcd(x,y)*y; if(x<0) x=-x; return x; } struct fraction { i64 a,b; fraction() {} fraction(i64 x) { a=x; b=1; } fraction(i64 x,i64 y) { a=x; b=y; deal(); } void deal() { if(b<0) b=-b,a=-a; i64 k=Gcd(a,b); if(k<0) k=-k; a/=k; b/=k; } fraction operator+(fraction p) { fraction ans; ans.b=Lcm(b,p.b); ans.a=ans.b/b*a+ans.b/p.b*p.a; ans.deal(); return ans; } fraction operator-(fraction p) { fraction ans; ans.b=Lcm(b,p.b); ans.a=ans.b/b*a-ans.b/p.b*p.a; ans.deal(); return ans; } fraction operator*(fraction p) { fraction ans; ans.a=a*p.a; ans.b=b*p.b; ans.deal(); return ans; } fraction operator/(fraction p) { fraction ans; ans.a=a*p.b; ans.b=b*p.a; ans.deal(); return ans; } void print() { printf("%lld/%lld\n",a,b); } }; fraction B[20]; i64 C[N][N]; void init() { int i,j; for(i=1;i<N;i++) { C[i][0]=C[i][i]=1; for(j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j]; } B[0]=fraction(1); for(i=1;i<=20;i++) { B[i]=fraction(0); for(j=0;j<i;j++) B[i]=B[i]-fraction(C[i+1][j])*B[j]; B[i]=B[i]/fraction(C[i+1][i]); } } int n; fraction a[N]; int main() { init(); Rush(n) { i64 i,L=1; for(i=0;i<=n;i++) { a[i]=fraction(C[n+1][i])*B[i]*fraction(1,n+1); L=Lcm(L,a[i].b); } printf("%lld ",L); a[1]=a[1]+fraction(1); for(i=0;i<=n;i++) printf("%lld ",L/a[i].b*a[i].a); puts("0"); } }