[原创]POJ 2429 GCD&LCM Inverse [pollard_rho]【数论】

2016-09-21 18:29:01 Tabris_ 阅读数：237

博客爬取于2020-06-14 22:43:13
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52611426

题目链接:http://poj.org/problem?id=2429

-----------------------------.
GCD & LCM Inverse
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 13908 Accepted: 2572
Description

Given two positive integers a and b, we can easily calculate the greatest common divisor (GCD) and the least common multiple (LCM) of a and b. But what about the inverse? That is: given GCD and LCM, finding a and b.
Input

The input contains multiple test cases, each of which contains two positive integers, the GCD and the LCM. You can assume that these two numbers are both less than 2^63.
Output

For each test case, output a and b in ascending order. If there are multiple solutions, output the pair with smallest a + b.
Sample Input

3 60
Sample Output

12 15

---------------------------------------------.
题目大意:
就是给你两个数的GCD和LCM值 让你求出和最小的这两个数

解题思路:
lcm=a/gcdb;
lcm/gcd=a/gcdb/gcd;

然后把lcm/gcd 这个结果质因子分解一下就行了
然后DFS求解和最小的值…

附本题代码
--------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*******************Miller_Rabin素数测试&&Pollard_rho整数分解**************************/
# include <cstdio>
# include <cmath>
# include <ctime>
# include <cstdlib>
# include <cstring>
# include <string>
# include <algorithm>
# include <iostream>
# define Times 11
# define MAX ((long long)1<<61)
# define N 501
# define C 201
# define LL long long
using namespace std;


int ct,cnt;
LL mini,jl[N],factor[N],num[N];
LL mina,minb,ans,n,m;

LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}

LL random(LL n){
    return (LL)((double)rand()/RAND_MAX*n+0.5);
}

LL multi(LL m,LL n,LL k){
    LL b=0;
    while(n){
        if(n&1) b=(b+m)%k;
        n>>=1;
        m=(m<<1)%k;
    }
    return b;
}

LL quick_mod(LL m,LL n,LL k){
    LL b=1;
    m%=k;
    while(n){
        if(n&1) b=multi(b,m,k);
        n/=2;
        m=multi(m,m,k);
    }
    return b;
}

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 false;
    while(j--){
        x=x*x%n;
        if(x==n-1) return false;
    }
    return true;
}

bool Miller_Rabin(LL n){
    if(n<2) return false;
    if(n==2) return true;
    if(!(n&1)) return false;
    for(int i=1;i<=Times;i++){
        LL a=random(n-2)+1;
        if(Witness(a,n)) return false;
    }
    return true;
}

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=(multi(x,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)){
        jl[++ct]=n;
        return ;
    }
    LL p=n;
    while(p>=n) p=Pollard_rho(p,k--);
    find(p,k);
    find(n/p,k);
}

void dfs(LL c,LL value){
    LL s=1,a,b;
    if(c==cnt+1){
        a=value;
        b=ans/a;
        if(gcd(a,b)==1){
            a*=n;
            b*=n;
            if(a+b<mini){
                mini=a+b;
                mina=a; minb=b;
            }
        }
        return ;
    }
    for(LL i=0;i<=num[c];i++){
        if(s*value>mini) return ;
        dfs(c+1,s*value);
        s*=factor[c];
    }
}

int main(){

//    freopen("data.in","r",stdin);
//    freopen("data.out","w",stdout);

//    srand(time(NULL));
    while(scanf("%lld%lld",&n,&m)!=EOF){
        if(n==m) {printf("%lld %lld\n",n,m); continue;}
        mini=MAX;
        ct=cnt=0;
        ans=m/n;
        find(ans,C);
        sort(jl+1,jl+ct+1);
        memset(factor,0,sizeof(factor));
        memset(num,0,sizeof(num));
        num[0]=1;
        factor[0]=jl[1];
        for(int i=2;i<=ct;i++){
            if(jl[i]!=jl[i-1]) factor[++cnt]=jl[i];
            num[cnt]++;
        }
        dfs(0,1);
        if(mina>minb) swap(mina,minb);
        printf("%lld %lld\n",mina,minb);
    }
    return 0;
}