Loading...

洛谷P2406 最小和

check评论:0 条 remove_red_eye浏览量:398 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-12-16

题意:给定$x=lcm(a,b),y=gcd(a,b)$,求$a+b$最小时$a,b$的值

因为$xy=gcd(x,y)\times lcm(x,y)$,我们先将$lcm(a,b),a,b$都除以$gcd(a,b)$

问题就转化为了$ab=x,gcd(a,b)=1$

因为$a+b$最小$ab$一定,所以$(a+b)^2$最小的话,$(a+b)^2-4ab$即$(a-b)^2$就最小

所以$a,b$要尽量靠近$\sqrt{lcm(a,b)}$

因为是$longlong$范围内,所以我们用$Pollard\ Rho$对其进行分解,然后再折半搜索组合答案就可以了

#include <bits/stdc++.h>
#define maxn 50
#define ll long long
#define ld long double
#define fi first
#define se second
using namespace std;
ll d[maxn],a,b;
map<ll,int> M;
ll mul(ll a,ll b,ll m)
{
    ll tmp=(ll)((ld)a*b/m+0.5),ret=a*b-tmp*m;
    return ret<0?ret+m:ret;
}
ll pw(ll a,ll b,ll m)
{
    ll ret=1;
    while(b)
    {
        if(b&1)
        {
            ret=mul(ret,a,m);
        } 
        a=mul(a,a,m),b>>=1;
    }
    return ret;
}
bool check(ll m,ll c)
{
    ll q=m-1,cnt=0;
    while(~q&1)
    {
        q>>=1,cnt++;
    }
    ll tmp=pw(c,q,m);
    if(tmp==1)
    {
        return true;
    }
    while(cnt--)
    {
        if(tmp==m-1)
        {
            return true;
        }
        tmp=mul(tmp,tmp,m);
    }
    return false;
}
bool Miller_Rabin(ll m)
{
    static int pr[]={0,2,3,5,7,11,13,131};
    for(int i=1;i<=7;i++)
    {
        if(pr[i]<m&&!check(m,pr[i]))
        {
            return false;
        }
    }
    return true;
}
void Pollard_Rho(ll m)
{
    static int pr[]={0,2,3,5,7,11,13};
    for(int i=1;i<=6;i++)
    {
        if(m%pr[i]==0)
        {
            return M[pr[i]]++,Pollard_Rho(m/pr[i]),void();
        }
    }
    if(m==1)
    {
        return;
    }
    if(Miller_Rabin(m))
    {
        return M[m]++,void();
    }
    for(ll c=1;c<=m-1;c++)
    {
        ll x=1,y=1;
        for(int i=1;;i++)
        {
            x=(mul(x,x,m)+c)%m;
            ll d=__gcd(m,abs(x-y));
            if(d!=1&&d!=m)
            {
                return Pollard_Rho(d),Pollard_Rho(m/d),void();
            }
            if(x==y)
            {
                break;
            }
            if((i&(-i))==i)
            {
                y=x;
            }
        }
    }
}
void solve()
{
    if(a==b)
    {
        return printf("%lld %lld\n",a,b),void();
    }
    M.clear(),Pollard_Rho(b/a);
    int cnt=0;
    for(auto &tmp:M)
    {
        d[cnt++]=pw(tmp.fi,tmp.se,b/a+1);
    }
    ll ans=1LL<<63-1,x,y;
    for(int s=0;s<1<<cnt-1;s++)
    {
        ll prod=1;
        for(int i=0;i<cnt;i++)
        {
            if(s&(1<<i))
            {
                prod*=d[i];
            }
        }
        if(prod+b/a/prod<ans)
        {
            ans=prod+b/a/prod,x=min(prod,b/a/prod)*a,y=max(prod,b/a/prod)*a;
        }
    }
    printf("%lld %lld\n",x,y);
}
int main()
{
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        solve();
    }    
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名