poj 2429 GCD & LCM Inverse（拉宾米勒测试+大数分解+dfs）

3 60

12 15

给出两个的最大公约数和最小公倍数 ?分别给出两个值 且这两个符合要求的值的和是最小的

lcm/gcd=(a/gcd)*(b/gcd) ? a/gcd与b/gcd是互素的 ?所以将lcm/gcd分解为两个互素的数 使这两个数和最小

将lcm/gcd进行分解 ?dfs出和最小的值

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <ctime>
#include <cstdlib>

#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 1010
#define MAXM 100010
#define INF 99999999
#define ll long long
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)
#define MAX ((ll)1<<61)
#define Times 10
#define C 201
using namespace std;

int Read()
{
    char ch;
    int a = 0;
    while((ch = getchar()) == ' ' | ch == 'n');
    a += ch - '0';
    while((ch = getchar()) != ' ' && ch != 'n')
    {
        a *= 10;
        a += ch - '0';
    }
    return a;
}

void Print(int a)    //ê?3?ía1ò
{
     if(a>9)
         Print(a/10);
     putchar(a%10+'0');
}
ll mini;
int cnt;
ll pri[MAXN];
ll key,gd,lm,res_a,res_b;

ll gcd(ll a,ll b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
ll random(ll n)
{
    return (ll)((double)rand()/RAND_MAX*n+0.5);
}
ll mult(ll a,ll b,ll m)//a*b%m
{
    ll ret=0;
    while(b>0)
    {
        if(b&1)
            ret=(ret+a)%m;
        b>>=1;
        a=(a<<1)%m;
    }
    return ret;
}
ll quick_mod(ll a,ll m)
{
    ll ans=1;
    a%=m;
    while(b)
    {
        if(b&1)
        {
            ans=mult(ans,a,m);
            b--;
        }
        b/=2;
        a=mult(a,m);
    }
    return ans;
}
bool Witness(ll a,ll n)
{
    ll m=n-1;
    int j=0;
    while(!(m&1))
    {
        j++;
        m>>=1;
    }
    ll x=quick_mod(a,m,n);
    if(x==1||x==n-1)
        return 0;
    while(j--)
    {
        x=x*x%n;
        if(x==n-1)
            return 0;
    }
    return 1;
}

bool miller_rabin(ll n)
{

//    cout<<"n "<<n<<endl;
    if(n<2) return 0;
    if(n==2) return 1;
    if(!(n&1))  return 0;
    for(int i=1;i<=Times;i++)
    {
        ll a=random(n-2)+1;
        if(Witness(a,n))  return 0;
    }
    return 1;
}
ll pollard_rho(ll n,int c)
{
    ll x,y,d,i=1,k=2;
    x=random(n-1)+1;
    y=x;
    while(1)
    {
        i++;
        x=(mult(x,n)+c)%n;
        d=gcd(y-x,n);
        if(1<d&&d<n)
            return d;
        if(y==x)
            return n;
        if(i==k)
        {
            y=x;
            k<<=1;
        }
    }
}
void find(ll n,int k)
{
    if(n==1)
        return;
    if(miller_rabin(n))
    {
        pri[++cnt]=n;
        return;
    }
    ll p=n;
    while(p>=n)
        p=pollard_rho(p,k--);
    find(p,k);
    find(n/p,k);
}

ll NumFactor[MAXN];
int Num[65],Len;
void dfs(int cur,ll value)
{
     ll s=1;
     if(cur==Len+1)
     {
         ll a=value;
         ll b=key/value;
         if(gcd(a,b)==1)
         {
             a*=gd;
             b*=gd;
             if(a+b<mini)
             {
                 mini=a+b;
                 res_a=a<b?a:b;
                 res_b=a>b?a:b;
             }
         }
         return;
     }
     for(int i=0;i<=Num[cur];i++)
     {
         if(value*s>=mini)
            return;
         dfs(cur+1,value*s);
         s*=NumFactor[cur];
     }
}
void solve(ll n)
{
    cnt=0;
    find(n,C);
    sort(pri+1,pri+1+cnt);
    Len=0;
    MEM(Num,0);
    Num[0]=1;
    NumFactor[0]=pri[1];
    for(int i=2;i<=cnt;i++)
    {
        if(NumFactor[Len]!=pri[i])
            NumFactor[++Len]=pri[i];
        Num[Len]++;
    }
    dfs(0,1);
}

int main()
{
    while(scanf("%lld%lld",&gd,&lm)!=EOF)
    {
        if(gd==lm)
        {
            printf("%lld %lldn",lm);
            continue;
        }
        mini=MAX;
        key=lm/gd;
        solve(key);
        printf("%lld %lldn",res_b);
    }
    return 0;
}