1 条题解

  • 0
    @ 2025-10-8 17:03:06

    一个显然的做法:由于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
    上传者