1 条题解

  • 1
    @ 2022-8-28 9:37:56
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<set>
    #include<map>
    #include<vector>
    #include<queue>
    using namespace std;
    #define ll long long
    #define RG register
    #define MAX 1111
    inline int read()
    {
        RG int x=0,t=1;RG char ch=getchar();
        while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
        if(ch=='-')t=-1,ch=getchar();
        while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
        return x*t;
    }
    struct BigInt
    {
    	int s[20000],ws;
    	void init(){s[1]=1;ws=1;}
    	void Multi(int x)
    	{
    		for(int i=1;i<=ws;++i)s[i]=s[i]*x;
    		for(int i=1;i<=ws;++i)s[i+1]+=s[i]/10,s[i]%=10;
    		while(s[ws+1])++ws,s[ws+1]=s[ws]/10,s[ws]%=10;
    	}
    	void output(){for(int i=ws;i;--i)printf("%d",s[i]);}
    }Ans1,Ans2;
    int pri[20001],tot;
    bool zs[20001];
    void getpri()
    {
    	zs[1]=true;
    	for(int i=2;i<=20000;++i)
    	{
    		if(!zs[i])pri[++tot]=i;
    		for(int j=1;j<=tot&&i*pri[j]<=20000;++j)
    		{
    			zs[i*pri[j]]=true;
    			if(i%pri[j]==0)break;
    		}
    	}
    }
    int Mul[20001],Div[20001];
    int sum,a[MAX];
    int n,m,D;
    void Calc(int x,int *f)
    {
    	for(int i=1;i<=tot;++i)
    		while(x%pri[i]==0)
    		{
    			f[pri[i]]++;
    			x/=pri[i];
    		}
    }
    int main()
    {
    	n=read();m=read();D=read();
    	for(int i=1;i<=n;++i)a[i]=read(),sum+=a[i];
    	getpri();
    	for(int i=1;i<=m;++i)
    	{
    		int x=read(),y=read();
    		if(!a[y]){puts("0/1");return 0;}
    		Calc(a[y],Mul);Calc(sum,Div);
    		a[y]+=D;sum+=D;
    	}
    	for(int i=1;i<=20000;++i)
    		if(Div[i]>=Mul[i])Div[i]-=Mul[i],Mul[i]=0;
    		else Mul[i]-=Div[i],Div[i]=0;
    	Ans1.init();Ans2.init();
    	for(int i=1;i<=20000;++i)
    		for(int j=1;j<=Mul[i];++j)Ans1.Multi(i);
    	for(int i=1;i<=20000;++i)
    		for(int j=1;j<=Div[i];++j)Ans2.Multi(i);
    	Ans1.output();putchar('/');Ans2.output();puts("");
    	return 0;
    }
    
    • 1

    信息

    ID
    1498
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    1
    已通过
    1
    上传者