NC17876. 多项式
描述
输入描述
两行，第一行为f，第二行为g。
f和g都用一个由小括号 '(' 和 ')' 、加号 '+' 、乘号 '*' 、 'x' 组成的表达式表示，表达式的语法与通常的习惯相同。
保证表达式的长度不超过1000。
输出描述
若答案为整数x，输出x/1，答案为+，输出1/0，否则输出表示答案的最简分数a/b。
示例1
输入:
x+x x+(x+x)
输出:
2/3
示例2
输入:
x*(x+x+x*x+x*x) x+(x+x)*(x+x+x)
输出:
1/0
示例3
输入:
x x*(x*(x)+x)*(((x+x)))*x
输出:
0/1
C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 4960K, 提交时间: 2018-08-29 23:01:09
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
#define LL long long
int ten[4] = {1,10,100,1000};
typedef struct BigNumber
{
int d[1200];
BigNumber(string s)
{
int i, j, k, len;
len = s.size();
d[0] = (len-1)/4+1;
for(i=1;i<=1199;i++)
d[i] = 0;
for(i=len-1;i>=0;i--)
{
j = (len-i-1)/4+1;
k = (len-i-1)%4;
d[j] += ten[k]*(s[i]-'0');
}
while(d[0]>1 && d[d[0]]==0)
--d[0];
}
BigNumber()
{
*this = BigNumber(string("0"));
}
string toString()
{
int i, j, temp;
string s("");
for(i=3;i>=1;i--)
{
if(d[d[0]]>=ten[i])
break;
}
temp = d[d[0]];
for(j=i;j>=0;j--)
{
s = s+(char)(temp/ten[j]+'0');
temp %= ten[j];
}
for(i=d[0]-1;i>0;i--)
{
temp = d[i];
for(j=3;j>=0;j--)
{
s = s+(char)(temp/ten[j]+'0');
temp %= ten[j];
}
}
return s;
}
}BigNumber;
BigNumber zero("0"), d, temp, mid[15];
bool operator < (const BigNumber &a, const BigNumber &b)
{
int i;
if(a.d[0]!=b.d[0])
return a.d[0]<b.d[0];
for(i=a.d[0];i>0;i--)
{
if(a.d[i]!=b.d[i])
return a.d[i]<b.d[i];
}
return 0;
}
bool operator == (const BigNumber &a, const BigNumber &b)
{
int i;
if(a.d[0]!=b.d[0])
return 0;
for(i=a.d[0];i>0;i--)
{
if(a.d[i]!=b.d[i])
return 0;
}
return 1;
}
BigNumber operator + (const BigNumber &a, const BigNumber &b)
{
int i, x;
BigNumber c;
c.d[0] = max(a.d[0], b.d[0]);
x = 0;
for(i=1;i<=c.d[0];i++)
{
x = a.d[i]+b.d[i]+x;
c.d[i] = x%10000;
x /= 10000;
}
while(x!=0)
{
c.d[++c.d[0]] = x%10000;
x /= 10000;
}
return c;
}
BigNumber operator - (const BigNumber &a, const BigNumber &b)
{
int i, x;
BigNumber c;
c.d[0] = a.d[0];
x = 0;
for(i=1;i<=c.d[0];i++)
{
x = 10000+a.d[i]-b.d[i]+x;
c.d[i] = x%10000;
x = x/10000-1;
}
while((c.d[0]>1) && (c.d[c.d[0]]==0))
--c.d[0];
return c;
}
BigNumber operator * (const BigNumber &a, const BigNumber &b)
{
int i, j, x;
BigNumber c;
c.d[0] = a.d[0]+b.d[0];
for(i=1;i<=a.d[0];i++)
{
x = 0;
for(j=1;j<=b.d[0];j++)
{
x = a.d[i]*b.d[j]+x+c.d[i+j-1];
c.d[i+j-1] = x%10000;
x /= 10000;
}
c.d[i+b.d[0]] = x;
}
while((c.d[0]>1) && (c.d[c.d[0]]==0))
--c.d[0];
return c;
}
bool smaller(const BigNumber &a, const BigNumber &b, int delta)
{
int i;
if(a.d[0]+delta!=b.d[0])
return a.d[0]+delta<b.d[0];
for(i=a.d[0];i>0;i--)
{
if(a.d[i]!=b.d[i+delta])
return a.d[i]<b.d[i+delta];
}
return 1;
}
void Minus(BigNumber &a, const BigNumber &b, int delta)
{
int i, x;
x = 0;
for(i=1;i<=a.d[0]-delta;i++)
{
x = 10000+a.d[i+delta]-b.d[i]+x;
a.d[i+delta] = x%10000;
x = x/10000-1;
}
while((a.d[0]>1) && (a.d[a.d[0]]==0))
--a.d[0];
}
BigNumber operator * (const BigNumber &a, int k)
{
BigNumber c;
c.d[0] = a.d[0];
int i, x;
x = 0;
for(i=1;i<=a.d[0];i++)
{
x = a.d[i]*k+x;
c.d[i] = x%10000;
x /= 10000;
}
while(x>0)
{
c.d[++c.d[0]] = x%10000;
x /= 10000;
}
while((c.d[0]>1) && (c.d[c.d[0]]==0))
--c.d[0];
return c;
}
BigNumber operator / (const BigNumber &a, const BigNumber &b)
{
int i, j, temp;
BigNumber c;
d = a;
mid[0] = b;
for(i=1;i<=13;i++)
mid[i] = mid[i-1]*2;
for(i=a.d[0]-b.d[0];i>=0;i--)
{
temp = 8192;
for(j=13;j>=0;j--)
{
if(smaller(mid[j], d, i))
{
Minus(d, mid[j], i);
c.d[i+1] += temp;
}
temp /= 2;
}
}
c.d[0] = max(1, a.d[0]-b.d[0]+1);
while((c.d[0]>1) && (c.d[c.d[0]]==0))
--c.d[0];
return c;
}
BigNumber Gcd(const BigNumber &a, const BigNumber &b)
{
BigNumber c("0");
if(b==c)
return a;
c = a-a/b*b;
return Gcd(b, c);
}
char str[1005], Q[1005];
typedef struct Res
{
BigNumber A, C;
Res operator + (const Res &b) const
{
Res temp = b;
if(C==b.C)
temp.C = b.C, temp.A = b.A+A;
else if(b.C<C)
temp.C = C, temp.A = A;
return temp;
}
Res operator * (const Res &b) const
{
Res temp;
temp.C = C+b.C;
temp.A = A*b.A;
return temp;
}
}Res;
Res Jud(LL L, LL R)
{
Res p;
LL i, now;
now = 0;
if(L==R)
{
BigNumber c1("1"), c2("1");
p.A = c1;
p.C = c2;
return p;
}
for(i=L;i<=R;i++)
{
if(str[i]=='(') now++;
if(str[i]==')') now--;
if(now==0 && str[i]=='+')
return Jud(L, i-1)+Jud(i+1, R);
}
for(i=L;i<=R;i++)
{
if(str[i]=='(') now++;
if(str[i]==')') now--;
if(now==0 && str[i]=='*')
return Jud(L, i-1)*Jud(i+1, R);
}
return Jud(L+1, R-1);
}
int main(void)
{
LL n;
Res p, q;
BigNumber t("0");
scanf("%s", str+1);
memcpy(Q, str, sizeof(Q));
n = strlen(str+1);
p = Jud(1, n);
scanf("%s", str+1);
if(strcmp(str+1, Q+1)==0)
printf("1/1\n");
else
{
n = strlen(str+1);
q = Jud(1, n);
if(p.C==q.C)
{
t = Gcd(p.A, q.A);
cout<<(p.A/t).toString()<<"/"<<(q.A/t).toString()<<endl;
}
else if(q.C<p.C)
printf("1/0\n");
else
printf("0/1\n");
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 2404K, 提交时间: 2018-08-17 20:57:40
#include<bits/stdc++.h>
using namespace std;
struct Int
{
int l,a[400];
Int operator+(const Int & b)const
{
Int t;
t.l=max(l,b.l);
memset(t.a,0,sizeof(t.a));
int i;
for(i=0;i<t.l;i++)t.a[i]=a[i]+b.a[i];
for(i=0;i<t.l;i++)if(t.a[i]>9)
{
t.a[i]-=10;
t.a[i+1]++;
}
if(t.a[t.l])t.l++;
return t;
}
Int operator-(const Int & b)const
{
Int t;
t.l=max(l,b.l);
memset(t.a,0,sizeof(t.a));
int i;
for(i=0;i<t.l;i++)t.a[i]=a[i]-b.a[i];
for(i=0;i<t.l;i++)if(t.a[i]<0)
{
t.a[i]+=10;
t.a[i+1]--;
}
for(;t.l&&!t.a[t.l-1];t.l--);
if(!t.l)t.l++;
return t;
}
bool operator>(const Int & b)const
{
if(l!=b.l)return l>b.l;
for(int i=l-1;~i;i--)if(a[i]!=b.a[i])return a[i]>b.a[i];
return 0;
}
Int operator*(const Int & b)const
{
Int t;
t.l=l+b.l-1;
memset(t.a,0,sizeof(t.a));
int i,j;
for(i=0;i<l;i++)for(j=0;j<b.l;j++)t.a[i+j]+=a[i]*b.a[j];
for(i=0;i<t.l;i++)if(t.a[i]>9)
{
t.a[i+1]+=t.a[i]/10;
t.a[i]%=10;
}
if(t.a[t.l])t.l++;
return t;
}
void operator>>=(int o)
{
int i;
for(i=l-1;i;i--)
{
if(a[i]&1)a[i-1]+=10;
a[i]>>=1;
}
a[0]>>=1;
if(!a[l-1])l--;
}
}x,y,z,o;
struct node
{
Int a;
int n;
node operator+(const node& y)const
{
node t;
if(n>y.n)t=*this;
else if(n<y.n)t=y;
else
{
t.a=a+y.a;
t.n=n;
}
return t;
}
node operator*(const node& y)const
{
node t;
t.n=n+y.n;
t.a=a*y.a;
return t;
}
}s[1005],a,b;
int n,i,t,t1;
char c[1005],s1[1005];
void work(node &ans)
{
scanf("%s",c);
n=strlen(c);
t=t1=0;
for(i=0;i<n;i++)if(c[i]=='x')
{
s[++t].n=1;
s[t].a=o;
}
else if(c[i]=='('||c[i]=='*')s1[++t1]=c[i];
else if(c[i]=='+')
{
while(t1&&s1[t1]=='*')
{
t--;
s[t]=s[t]*s[t+1];
t1--;
}
s1[++t1]='+';
}
else
{
for(;s1[t1]!='(';)
{
t--;
if(s1[t1]=='+')s[t]=s[t]+s[t+1];
else s[t]=s[t]*s[t+1];
t1--;
}
t1--;
}
for(;t>1;t--,t1--)if(s1[t1]=='+')s[t-1]=s[t-1]+s[t];
else s[t-1]=s[t-1]*s[t];
ans=s[1];
}
void gcd(Int x,Int y,Int &a,Int &b)
{
if(y>x)
{
gcd(y,x,b,a);
return;
}
if(y.l==1&&!y.a[0])
{
a.l=b.l=1;
memset(a.a,0,sizeof(a.a));
memset(b.a,0,sizeof(b.a));
a.a[0]=1;
return;
}
if((x.a[0]&1)&&(y.a[0]&1))
{
gcd(x-y,y,a,b);
a=a+b;
}
else if(x.a[0]&1)
{
y>>=1;
gcd(x,y,a,b);
b=b*o;
}
else if(y.a[0]&1)
{
x>>=1;
gcd(x,y,a,b);
a=a*o;
}
else
{
x>>=1;
y>>=1;
gcd(x,y,a,b);
}
}
void out(Int x)
{
for(int i=x.l-1;~i;i--)printf("%d",x.a[i]);
}
int main()
{
o.l=o.a[0]=1;
work(a);
work(b);
if(a.n>b.n)puts("1/0");
else if(a.n<b.n)puts("0/1");
else
{
o.a[0]=2;
x=a.a;
y=b.a;
gcd(x,y,x,y);
out(x);
putchar('/');
out(y);
}
return 0;
}
Java(javac 1.8) 解法, 执行用时: 56ms, 内存消耗: 12492K, 提交时间: 2018-08-18 11:35:14
import java.math.BigInteger;
import java.util.Scanner;
class node{
BigInteger x;
int c;
public void add(node b) {
if(b.c<c)return;
if(b.c>c) {
x=b.x;
c=b.c;
}else {
x=x.add(b.x);
}
}
public void mul(node b) {
x=x.multiply(b.x);
c+=b.c;
}
}
public class Main {
public static node cal(String x) {
node num[]=new node[1010];
int op[]=new int[1010];
int sz=x.length(),now=0,opn=0;
for(int i=0;i<1010;++i)num[i]=new node();
for(int i=0;i<sz;++i) {
if(x.charAt(i)=='x') {
num[now].x=BigInteger.ONE;
num[now].c=1;
++now;
}else if(x.charAt(i)=='+') {
while(opn>0 && op[opn-1]==2) {
num[now-2].mul(num[now-1]);
--now;
--opn;
}
op[opn]=1;
++opn;
}else if(x.charAt(i)=='*') {
op[opn]=2;
++opn;
}else if(x.charAt(i)=='(') {
op[opn]=3;
++opn;
}else if(x.charAt(i)==')') {
while(opn>0 && op[opn-1]!=3) {
if(op[opn-1]==1) {
num[now-2].add(num[now-1]);
}else {
num[now-2].mul(num[now-1]);
}
--now;
--opn;
}
--opn;
}
}
while(opn>0) {
if(op[opn-1]==1) {
num[now-2].add(num[now-1]);
}else {
num[now-2].mul(num[now-1]);
}
--now;
--opn;
}
return num[0];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in=new Scanner(System.in);
String a=in.nextLine(),b=in.nextLine();
node la=cal(a);
node lb=cal(b);
if(la.c>lb.c) {
System.out.println("1/0");
}else if(la.c<lb.c) {
System.out.println("0/1");
}else {
BigInteger gcd=la.x.gcd(lb.x);
System.out.println(la.x.divide(gcd)+"/"+lb.x.divide(gcd));
}
}
}
Python3(3.5.2) 解法, 执行用时: 40ms, 内存消耗: 3692K, 提交时间: 2018-08-17 22:01:26
class pair:
def __init__(self,f,s):
self.fi=f
self.se=s
def gcd(a,b):
if b==0:
return a
else:
return gcd(b,a%b)
def prio(x):
if x=='*':
return 2
elif x=='+':
return 1
elif x=='(' or x==')':
return 0
else:
return -1
def fun(s):
sv,sp=[],[]
k,flag=0,1
x=pair(0,0)
y=pair(0,0)
s+='\0'
sp.append('\0')
c=s[k]
while flag!=0:
# print(len(sv))
# print(k)
if c=='x':
sv.append(pair(1,1))
k+=1
elif c=='\0' and sp[-1]=='\0':
flag=0
elif c=='('or prio(c)>prio(sp[-1]):
sp.append(c)
k+=1
elif c==')' and sp[-1]=='(':
sp.pop();
k+=1
elif prio(c)<=prio(sp[-1]):
x=sv[-1]
sv.pop()
y=sv[-1]
sv.pop()
c=sp[-1]
sp.pop()
if c=='+':
if x.fi==y.fi:
y.se=x.se+y.se
elif x.fi>y.fi:
y=x;
else:
y=pair(x.fi+y.fi,x.se*y.se)
# print(x.fi,x.se,y.fi,y.se)
sv.append(y)
c=s[k]
return sv[-1]
s1=input()
s2=input()
x1,x2=fun(s1),fun(s2)
if x1.fi==x2.fi:
g=gcd(x1.se,x2.se)
print("%d/%d"%(x1.se//g,x2.se//g))
elif x1.fi>x2.fi:
print("1/0")
else:
print("0/1")
Python(2.7.3) 解法, 执行用时: 42ms, 内存消耗: 3192K, 提交时间: 2018-08-17 21:14:11
def add(a,b):
s=[0]*max(len(a),len(b))
for i in xrange(0,len(a)):
s[i]+=a[i]
for i in xrange(0,len(b)):
s[i]+=b[i]
return s
def mul(a,b):
s=[0]*(len(a)+len(b)-1)
for i in xrange(0,len(a)):
for j in xrange(0,len(b)):
s[i+j]+=a[i]*b[j]
return s
def build(s):
if s=="x":
return [0,1]
x=0
for i in xrange(0,len(s)):
if s[i]=='(':
x+=1
elif s[i]==')':
x-=1
elif x==0 and s[i]=='+':
return add(build(s[:i]),build(s[i+1:]))
for i in xrange(0,len(s)):
if s[i]=='(':
x+=1
elif s[i]==')':
x-=1
elif x==0 and s[i]=='*':
return mul(build(s[:i]),build(s[i+1:]))
return build(s[1:-1])
def gcd(a,b):
while b:
a,b=b,a%b
return a
a=raw_input()
b=raw_input()
xa=build(a)
xb=build(b)
if len(xa)>len(xb):
print '1/0'
elif len(xa)<len(xb):
print '0/1'
else:
A=xa[-1]
B=xb[-1]
g=gcd(A,B)
A/=g
B/=g
print str(A)+"/"+str(B)