1 条题解
-
0
一个显然的做法:由于pi两两互质,所以我们可以从后向前扫,令tmp[i]=tmp[i+1](p[i]-1)/p[i],则ans[i]=tmp[i+1]/p[i]。显然鉴于p[i]和n的大小,直接做肯定是要爆longlong的,而直接上高精度约分时间复杂度接受不了。所以当我们想求(a/b)(C/D)时,其中C,D为高精度数并且已经约分完毕,a,b是低精度数,则我们可以让a和D约分,b和C约分,这样就转化成了高精度与低精度取gcd了,时间复杂度也就得到了保证。注意当答案为0的时候要输出"0/1"。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 1010 #define M 1000000000 using namespace std; struct ppp { long long a[4010],clong; void jinwei() { int i; for(i=1;i<clong;i++) { a[i+1]+=a[i]/M; a[i]%=M; } while(a[clong]>=M) { clong++; a[clong]=a[clong-1]/M; a[clong-1]%=M; } while(a[clong]==0&&clong>1) clong--; } void print() { int i; printf("%d",a[clong]); for(i=clong-1;i>=1;i--) printf("%09d",a[i]); } }; void make(ppp &x,int y) { x.clong=1; x.a[1]=y; } int operator %(const ppp &x,int y) { long long ret=0; int i; for(i=x.clong;i>=1;i--) ret=(ret*M+x.a[i])%y; return (int)ret; } ppp ret; ppp operator *(const ppp &x,int y) { int i; for(i=1;i<=ret.clong;i++) ret.a[i]=0; ret.clong=x.clong; for(i=1;i<=x.clong;i++) ret.a[i]=x.a[i]*y; ret.jinwei(); return ret; } ppp operator /(const ppp &x,int y) { int i; for(i=1;i<=ret.clong;i++) ret.a[i]=0; long long tmp=0; ret.clong=x.clong; for(i=x.clong;i>=1;i--) { tmp=tmp*M+x.a[i]; ret.a[i]=tmp/y; tmp%=y; } ret.jinwei(); return ret; } int a[N]; ppp A[N],B[N]; ppp tmpa,tmpb; int gcd(int a,int b) { if(!a) return b; return gcd(b%a,a); } int gcd(int a,const ppp &b) { int tmp=b%a; return gcd(a,tmp); } int main() { int n; scanf("%d",&n); int i,j,x,y; for(i=1;i<=n;i++) scanf("%d",&a[i]); make(A[n],1);make(B[n],a[n]); make(tmpa,a[n]-1);make(tmpb,a[n]); int D=0; for(i=n-1;i>=1;i--) { x=a[i]-1;y=a[i]; int X,Y; if(x!=0) { X=gcd(x,tmpb);Y=gcd(y,tmpa); x/=X;y/=Y; A[i]=tmpa/Y; B[i]=tmpb*y; tmpa=A[i]*x; tmpb=B[i]/X; } else { D=i-1; A[i]=tmpa; B[i]=tmpb; break; } } for(i=1;i<=D;i++) puts("0/1"); for(i=D+1;i<=n;i++) { A[i].print(); printf("/"); B[i].print(); puts(""); } }
- 1
信息
- ID
- 2781
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 8
- 标签
- 递交数
- 38
- 已通过
- 5
- 上传者