fractio专题

2020牛客暑期多校第三场 F-Fractio Construction Problem(扩展欧几里得)

题目戳这里 题意: 分情况讨论下: 1.设g=gcd(a,b),若g > 1,即不为最简分式,此时直接令d = b/g,c = a+b,e = f = 1,即可因为此时构造是满足d < b并且f < b的 2.g = 1,此时分式为最简分式,但如果 b 不能分解出两个不一样的质因子,此时就无法完成构造,直接输出-1 3.g = 1,但是此时b有两个不同质因数,通分后分子上即可变为cf-de =