答案+题目分析

Kinghero King of the summit 2021-10-10 9:19:47 2023-11-07 17:43:50 6
    //这是一道纯数学题,首先声明一下要long long(我开始还把scanf的lld写成了ld)
    //这道题重点在于x,y上界看似是“不确定”的,所以我们先要求出一个明确的上界:
    //因为 x<=y,那么 1/x>=1/y
    //又因为x,y均为正整数,所以 1/x>0,1/y>0
    //显然,如果1/x>1/k 即 x<k,则1/y为负,违背了题意,如果x=k则1/y=0,无解
    //由此确定x的下界为k+1,k<x
    //接下来确定上界:
    //因为1/x>=1/y 故1/x>=1/2k 很容易得出x<=2k<=y
    //综上所述,有k<x<=2k<=y
    //知道了x,y就能很轻松的求出了,通分就好:
    // 1/k-1/x=x-k/kx
    //根据题意,x-k/kx应为分子为1的分数,那么kx必须整除x-k
    //逐个枚举即可
    //该算法的时间复杂度为O(k),完全能过,耗时不过20Ms
    //分析到这里,应该可以写程序了,再说一遍,要用long long!:
    for (i = k + 1; i &lt;= 2 * k; i++)
        if ((k * i) % (i - k) == 0)
            printf("1/%lld=1/%lld+1/%lld\n", k, i, k * i / (i - k));

{{ vote && vote.total.up }}