poj 2429 GCD & LCM Inverse

这道题WA了我好多次，就像比赛的时候一样，都是些小错误，但oj是无情的，让我一W再W；

当时正和安叔聊着天，安叔一直在批评我们平时做题很水，太依赖死东西了。

以后真的不能再依赖模板了```

说说这题吧。思路很容易想到```我刚刚开始直接用gcd的办法，超时了，没办法，数据很大```

先算出/g=a/b；然后对g用那个Pollard_rho算法得出所有的素因数，排序，把相同的元素结合在一起；

这样可以保证待会儿分解的时候不会有相同的因数；

分解的时候，从g的平方根开始用dfs，很简单```

贴下代码：

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<stdlib.h>
  5 #include<cmath>
  6 #define LL long long
  7 using namespace std;
  8 const int s=20;
  9 LL tol,co;
 10 LL factor[100],ans,ss[100];
 11 
 12 LL mult_mod(LL a,LL b,LL c)//计算a*b%c;
 13 {
 14     LL ret=0;
 15     a%=c;
 16     b%=c;
 17     while(b>0)
 18     {
 19         if(b&1) ret=(ret+a)%c;
 20         a<<=1;
 21         if(a>=c) a%=c;
 22         b>>=1;
 23     }
 24     return ret;
 25 }
 26 
 27 LL pow_mod(LL a,LL b,LL mod)//计算a^b%b
 28 {
 29     if(b==1) return a%mod;
 30     a%=mod;
 31     LL tmp=a;
 32     LL ret=1;
 33     while(b>0)
 34     {
 35         if(b&1) ret=mult_mod(ret,tmp,mod);
 36         tmp=mult_mod(tmp,tmp,mod);
 37         b>>=1;
 38     }
 39     return ret;
 40 }
 41 
 42 //以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
 43 //一定是合数返回true,不一定返回false
 44 bool check(LL a,LL n,LL x,LL t)
 45 {
 46     LL ret=pow_mod(a,x,n);
 47     LL last=ret;
 48     for(int i=1; i<=t; i++)
 49     {
 50         ret=mult_mod(ret,ret,n);
 51         if(ret==1&&last!=1&&last!=n-1) return 1;
 52         last=ret;
 53     }
 54     if(ret!=1) return 1;
 55     return false;
 56 }
 57 
 58 // Miller_Rabin()算法素数判定
 59 //是素数返回true.(可能是伪素数，但概率极小)
 60 //合数返回false;
 61 bool Miller_Rabin(LL a)
 62 {
 63     if(a<2) return 0;
 64     if(a==2) return 1;
 65     if((a&1==0)) return 0;
 66     LL x=a-1;
 67     LL t=0;
 68     while((x&1)==0)
 69     {
 70         x>>=1;
 71         t++;
 72     }
 73     for(int i=0; i<s; i++)
 74     {
 75         long long b=rand()%(a-1)+1;
 76         if(check(b,a,x,t))
 77             return 0;
 78     }
 79     return 1;
 80 }
 81 
 82 LL gcd(LL a,LL b)
 83 {
 84     if(a==0)return 1;
 85     if(a<0) return gcd(-a,b);
 86     while(b)
 87     {
 88         LL t=a%b;
 89         a=b;
 90         b=t;
 91     }
 92     return a;
 93 }
 94 
 95 LL Pollard_rho(LL x,LL c)
 96 {
 97     LL i=1,k=2;
 98     LL x0=rand()%x;
 99     LL y=x0;
100     while(1)
101     {
102         i++;
103         x0=(mult_mod(x0,x0,x)+c)%x;
104         LL d=gcd(y-x0,x);
105         if(d!=1&&d!=x) return d;
106         if(y==x0) return x;
107         if(i==k)
108         {
109             y=x0;
110             k+=k;
111         }
112     }
113 }
114 
115 void findfac(LL n)
116 {
117     if(Miller_Rabin(n))//素数
118     {
119         factor[tol++]=n;
120         return;
121     }
122     LL p=n;
123     while(p>=n)p=Pollard_rho(p,rand()%(n-1)+1);
124     findfac(p);
125     findfac(n/p);
126 }
127 
128 void findx(LL i,LL x,LL q)
129 {
130     if(x>q) return;
131     if(x>ans) ans=x;
132     for(LL j=i;j<=co;j++)
133         if(x*ss[j]<=q) findx(j+1,x*ss[j],q);
134 }
135 
136 int main()
137 {
138     LL a,b;
139     while(scanf("%lld%lld",&a,&b)!=EOF)
140     {
141         memset(factor,0,sizeof factor);
142         memset(ss,0,sizeof ss);
143         if(a==b) {printf("%lld %lld
",a,b);continue;}
144         if(a>b)
145         {
146             a=a^b;
147             b=a^b;
148             a=a^b;
149         }
150         LL g=b/a;
151         tol=0;
152         findfac(g);
153         sort(factor,factor+tol);
154         ss[0]=factor[0];
155         co=0;
156         for(int i=1;i<tol;i++)
157         {
158             if(factor[i]==factor[i-1]) ss[co]*=factor[i];
159             else
160             {
161                 co++;
162                 ss[co]=factor[i];
163             }
164         }
165         LL q=sqrt(1.0*g);
166         ans=1;
167         findx(0,1,q);
168         printf("%lld %lld
",ans*a,g/ans*a);
169     }
170     return 0;
171 }

View Code