HDU 5584- LCM Walk 【数论】

你的名字 2023-08-17 17:29 129阅读 0赞

题意：给你一个x和y，z = lcm(x, y)，每次x加上z或者y加上z，然后给你一个终点，问你最多能从几个点转移过来的。

思路：对于给定的终点(x, y) , 我们可以知道一定是较大那个数加上了z，所以我们令y为较大那个数。设(x, y1) 是上次的点，

g = gcd(x, y1）， z = lcm(x, y1) = k\*x , 那么y1 = k \* gcd(x, y),  gcd(x, y) = gcd(x, y - kx)

所以 y- z = z / x \* g, 则 z = x \* y / (x + g),就可以求解了。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define mid ((l + r) >> 1)
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 100;
    const int mod = 1e9 + 7;
    
    ll gcd(ll a, ll b)
    {
        return b == 0 ? a : gcd(b, a % b);
    }
    int slove(ll x, ll y)
    {
        int ret = 1;
        if(x > y) swap(x, y);
        ll g = gcd(x, y);
        while(y % (x + g) == 0)
        {
            if(x < 1 || y < 1) break;
            ++ret;
            y = y - y * x / (x + g);
            if(x > y) swap(x, y);
        }
        return ret;
    }
    
    int main()
    {
        int t, t1 = 1;
        scanf("%d", &t);
        while(t--)
        {
            printf("Case #%d: ", t1++);
            ll x, y;
            scanf("%lld%lld", &x, &y);
            printf("%d\n", slove(x, y));
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，129人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 5584- LCM Walk 【数论】

题意：给你一个x和y，z = lcm(x, y)，每次x加上z或者y加上z，然后给你一个终点，问你最多能从几个点转移过来的。思路：对于给定的终点(x, y) , 我们可以知

你的名字/ 2023年08月17日 17:29/ 0 赞/ 129 阅读

相关 HDU Walk （概率DP）

HDU Walk （概率DP）：[http://acm.hdu.edu.cn/showproblem.php?pid=5001][http_acm.hdu.edu.cn_sho

柔光的暖阳◎/ 2022年08月21日 11:58/ 0 赞/ 238 阅读

相关 51nod 1434 数论区间LCM问题

题意：一个整数序列S的LCM（最小公倍数）是指最小的正整数X使得它是序列S中所有元素的倍数，那么LCM(S)=X。例如，LCM(2)=2,LCM(4,6)=12,LCM

川长思鸟来/ 2022年08月19日 15:13/ 0 赞/ 258 阅读

相关数论 Lucas定理 hdu3037

对于C(n, m) mod p。这里的n，m，p（p为素数）都很大的情况。就不能再用C(n, m) = C(n - 1，m) + C(n - 1, m - 1)的公式递推了。

àì夳堔傛蜴生んèń/ 2022年08月18日 01:58/ 0 赞/ 220 阅读

相关 HDU 5495 LCS（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5495 参考博客： http://blog.csdn.net/queue

小咪咪/ 2022年08月09日 01:59/ 0 赞/ 181 阅读

相关 HDU 5750 Dertouzos（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5750 题目大意：x能整除n，x就是n的positive proper div

谁借莪１个温暖的怀抱￠/ 2022年07月20日 12:15/ 0 赞/ 155 阅读

相关 HDU 5755 Gambler Bo（数论）

题目链接： http://acm.split.hdu.edu.cn/showproblem.php?pid=5755 题目大意：给你一个矩阵，矩阵中是0，1，2三个

素颜马尾好姑娘i/ 2022年07月16日 23:27/ 0 赞/ 203 阅读

相关 HDU 5768 Lucky7（数论）

题目链接： http://acm.split.hdu.edu.cn/showproblem.php?pid=5768 题目大意：求出一个区间内模7余0，但是模一些给定的互

电玩女神/ 2022年07月16日 23:26/ 0 赞/ 205 阅读

相关 HDU 5584 LCM Walk （数学推导）（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5584 题目大意：给你一个点(x，y),你每次可以向前走z，z为x和y的最小公

痛定思痛。/ 2022年07月16日 03:15/ 0 赞/ 181 阅读

相关 HDU 3988(数论)

问题描述: iSea is tired of writing the story of Harry Potter, so, lucky you, solving the fo

浅浅的花香味﹌/ 2022年05月31日 05:06/ 0 赞/ 213 阅读