bzoj 2852: 强大的区间

yy了一下居然能a。。
真神奇。
发现我的python水平完全没有了。。
写的python代码一副浓浓的c风格。。

一些推导

这题实际上是给两个非负实数
求不等式的最小正整数解:

首先,如果
显然k=1就是最小整数解。
否则我们假设(x,y分别是a,b的整数部分,{a}表示a的小数部分)
显然x=y(因为x< y的情况已经讨论过了,而因为a< b,所以x一定不大于y)

那么不等式等价于

因为x=y。所以就是

取个倒数推一推就能推出递归关系了。。
(太困了懒得详细写了。。)

大概就是说我们设A是a的小数部分的倒数,B是b的小数部分的倒数。。
如果找到了一个最小的整数T,满足

那么不等式

的最小整数解一定满足

总之递归就好了。。推导不难。以后再补。。

代码很丑。。。其实也不需要gcd搞既约分数的。。

已经是第n次在bzoj因为这个错误wa了。。

tmp=raw_input().split(' ');

关键是本机运行挺正常的T_T

#!/usr/bin/python

def gcd(x,y):
    while(y!=0):
        x,y=y,x%y
    return x
def trans(num):
    L=len(num)
    X=0
    Y=1
    flag=0
    for i in range(L):
        if(num[i]=='.'):
            flag=1
            continue
        X=X*10+int(num[i])
        if(flag):Y*=10
    d=gcd(X,Y)
    X/=d
    Y/=d
    return (X,Y)
def calc(a,A,b,B):
    #find k,that satisfies ceil(k*(a/A))<=floor(k*(b/B))

    if(a%A==0):
        return 1
    if(b%B==0):
        return 1
    X1=a/A
    X2=b/B
    if(X1<X2):
        return 1
    if(X1>0):
        a-=A*X1
        b-=B*X2
    T=calc(B,b,A,a)
    return (B*T+b-1)/b
def solve(A,B):
    return calc(A[0],A[1],B[0],B[1])
tmp=raw_input().split();
print solve(trans(tmp[0]),trans(tmp[1]))

Comments

comments powered by Disqus