HDU5974 - The 2016 ACM-ICPC Asia Dalian Regional Contest - D - A Simple Math Problem - （数论LCM，dfs）

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

题意：给出a和b，让找到X和Y满足：

1. X+Y=a；
2. LCM（X，Y）=b；

LCM为最小公倍数，(1≤a≤2*10^4)，(1≤b≤10^9)，注意：测试样例很多。

解析：

 所以这里知道了b之后就有了一种枚举X与Y的方式:

综上dfs枚举X，Y判断是否等于a即可。但是上述方法复杂度是比较高的，看别的题解上都是推了个公式解一下来直接求的X,Y，时间用的会少一些。

最后注意题目中的超级大巨坑：最后输出的X，Y一定保证小的在前。这一点比赛时卡了我一个多小时，TMD。

代码（719ms）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool flag;
ll a,b,len,ansx,ansy;
ll p[105],num[105];

void init(ll n)//分解质因子
{
    len=0;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            p[++len]=i;
            num[len]=0;
        }
        while(n%i==0)
        {
            num[len]++;
            n=n/i;
        }
    }
    if(n>1)
    {
        p[++len]=n;num[len]=1;
    }
}

ll fpow(ll n,ll x)//求n^x
{
    ll ans=1;
    for(int i=1;i<=x;i++)
        ans=ans*n;
    return ans;
}

//step是当前处理到第step个因子，sum1是X前step-1项的累乘，sum2是Y前step-1项的累乘
void dfs(ll step,ll sum1,ll sum2)
{
    //x的第step项取p[step]^i，此时Y的第step 项一定是p[step]^num[step]
    for(int i=0;i<num[step];i++)
    {
        if(flag) return;
        if(step<len)
        {
            dfs(step+1,sum1*fpow(p[step],i),sum2*fpow(p[step],num[step]));
        }
        else
        {
            ll x=sum1*fpow(p[step],i);
            ll y=sum2*fpow(p[step],num[step]);
            //cout<<x<<"            "<<y<<endl;
            if(x+y==a)
            {
                flag=true;
                ansx=x;ansy=y;
                return;
            }
        }
    }

    //x的第step项固定取p[step]^num[step]，然后枚举Y的第step项
    for(int i=0;i<=num[step];i++)
    {
        if(flag) return;
        if(step<len)
        {
            dfs(step+1,sum1*fpow(p[step],num[step]),sum2*fpow(p[step],i));
        }
        else
        {
            ll x=sum1*fpow(p[step],num[step]);
            ll y=sum2*fpow(p[step],i);
            //cout<<x<<" "<<y<<endl;
            if(x+y==a)
            {
                flag=true;
                ansx=x;ansy=y;
                return;
            }
        }
    }
}

int main()
{
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        if(a==1)
        {
            printf("No Solution\n");
            continue;
        }
        if(b==1)
        {
            if(a==2)
                printf("1 1\n");
            else
                printf("No Solution\n");
            continue;
        }
        init(b);
        flag=false;
        dfs(1ll,1ll,1ll);
        if(flag)
        {
            if(ansx>ansy) swap(ansx,ansy);
            printf("%lld %lld\n",ansx,ansy);
        }
        else
            printf("No Solution\n");
    }
    return 0;
}