1 条题解
-
1
#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
- 3135
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者