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

痛定思痛。 2022-07-16 03:15 123阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5584

题目大意：给你一个点(x，y),你每次可以向前走z，z为x和y的最小公倍数，即走到(x+z,y)或者(x,y+z)，现在给你一个点(x,y)问你可能的出发点有几个（包括自己）

解题思路：  
因为z=lcm(x,y)  
所以z>=x &&z>=y  
所以假设在点（x,y）时，大的点一定是上一步加上z的点。

假设y>x,那么y=y1+z,z=lcm(y1,x) 假设z=k\*x

那么 (y1\*x)/(gcd(y1,x))=k\*x  
y1/(gcd(y1,x))=k;

注意到gcd(x,y)=gcd(x,y-k\*x) k为整数

gcd(y1,x)=gcd(y-kx,x)=gcd(y,x)

y1=k\*gcd(y,x)

y-z=z/x*gcd(y,x)  
yx-zx=z*gcd(x,y)

z=(y\*x)/(x+gcd(x,y))  
既然求出了z那么剩下的就好做了

我并不是这么AC的，我当时不知道gcd(y1,x)=gcd(y-kx,x)=gcd(y,x)，所以我在这里枚举了k的值，注意到10亿的因子只有100个，所以也没超时。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <set>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    vector<LL> p;
    LL cal(LL x,LL y)
    {
        return x*y/__gcd(x,y);
    }
    void find_yinshu(LL x)
    {
        p.clear();
        LL t=floor(sqrt(x)+0.5);
        for(LL i=1; i<=t; i++)
        {
            if(x%i==0)
            {
                p.push_back(i);
                if(i*i!=x)
                {
                    p.push_back(x/i);
                }
            }
        }
        sort(p.begin(),p.end());
    }
    int main()
    {
        int T,cas=1;
        RI(T);
        while(T--)
        {
            LL x,y;
            scanf("%I64d %I64d",&x,&y);
            int ans=1;
            while(1)
            {
                if(x<y) swap(x,y);
                //cout<<x<<"    "<<y<<endl;
                bool mark=false;
                if(x%y==0)
                {
                    LL d=x/y;
                    while(d%2==0)
                    {
                        d/=2;
                        ans++;
                    }
                    break;
    
                }
                else
                {
                    find_yinshu(x);
                    for(int i=0;i<p.size();i++)
                    {
                        if(x-p[i]*y<=0) break;
                        if((p[i]*y)%(x-p[i]*y)==0)
                        {
                            LL x1=x-p[i]*y;
                            if(x1+cal(x1,y)==x)
                            {
                                x=x1;
                                mark=true;
                                break;
                            }
                        }
    
                    }
                    if(mark) ans++;
                    else break;
                }
            }
            printf("Case #%d: %d\n",cas++,ans);
    
        }
    
        return 0;
    }