2014/3/31 长沙多校（第五次）

  1 /*1543*/
  2 #include <iostream>
  3 #include <string.h>
  4 #include <stdio.h>
  5 #include <stdlib.h>
  6 #include <algorithm>
  7 #include <ctime>
  8 #include <cmath>
  9 #include <set>
 10 #define maxn 51000
 11 #define LL long long
 12 using namespace std;
 13 const int Times = 10 ;
 14 const int C = 777 ;
 15 LL N;
 16 LL a[70];
 17 LL b[70];
 18 LL pri[maxn];
 19 LL cnt;
 20 set<LL> S;
 21 
 22 LL MIN(LL a,LL b) { return a<b?a:b; }
 23 
 24 LL ABS(LL a) { return a>0?a:-a; }
 25 
 26 LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); }
 27 
 28 LL mul_mod(LL a,LL b,LL n)
 29 {
 30     LL ans=0;
 31     while (b>0)
 32     {
 33         if (b&1) ans+=a;
 34         if (ans>n) ans-=n;
 35         a<<=1;
 36         if (a>n) a-=n;
 37         b>>=1;
 38     }
 39     return ans;
 40 }
 41 
 42 LL exp_mod(LL a,LL b,LL n)
 43 {
 44     LL ans=1;
 45     while (b>0)
 46     {
 47         if (b&1) ans=mul_mod(ans,a,n);
 48         a=mul_mod(a,a,n);
 49         b>>=1;
 50     }
 51     return ans;
 52 }
 53 
 54 bool miller_rabbin(LL n)
 55 {
 56     if (n==2) return true;
 57     if (n<2 || !(n&1)) return false;
 58     int t=0;
 59     LL u=n-1,a,x,y;
 60     while (!(u&1)) t++,u>>=1;
 61     for (int i=0; i<=Times; i++)
 62     {
 63         a=rand()%(n-1)+1;
 64         if (a<0 || a==1) a=n/2;
 65         if (exp_mod(a,n-1,n)!=1)  return false;
 66         x=exp_mod(a,u,n);
 67         for (int j=0; j<t; j++)
 68         {
 69             y=mul_mod(x,x,n);
 70             if (y==1 && x!=1 && x!=n-1) return false;
 71             x=y;
 72         }
 73         if (x!=1) return false;
 74     }
 75     return true;
 76 }
 77 
 78 LL pollar_rho(LL n,LL c)
 79 {
 80     LL d,x,y,i=1,k=2;
 81     x=rand()%(n-1)+1;
 82     if (x<0) x=-x;
 83     y=x;
 84     while (1)
 85     {
 86         i++;
 87         x=(mul_mod(x,x,n)+c)%n;
 88         d=gcd(ABS(x-y),n);
 89         if (d>1 && d<n) return d;
 90         if (x==y) return n;
 91         if (i==k)
 92             y=x,k<<=1;
 93     }
 94 }
 95 
 96 
 97 void find(LL n,LL k)
 98 {
 99     if (n==1) return;
100     if (miller_rabbin(n)) { pri[cnt++]=n; return; }
101     LL p=n;
102     while (p>=n) p=pollar_rho(p,k--);
103     find(p,k);
104     find(n/p,k);
105 }
106 
107 void find_max_exp(LL p){
108     int pos=-1,m=-1;
109     for(int i=0;i<N;i++){
110         int k=0;
111         LL an=a[i];
112         while(an%p==0){
113             k++;
114             an=an/p;
115         }
116         if ((k>m) || (k==m && i>pos)) {
117             pos=i;m=k;
118         }
119     }
120     while(m--){
121         b[pos]=b[pos]*p;
122     }
123 //    cout<<"p="<<p<<","<<"pos="<<pos<<endl;
124 }
125 int main(){
126     while(cin>>N && N>0){
127         cnt=0;
128         for(int i=0;i<N;i++){
129             cin>>a[i];
130             find(a[i],C);
131         }
132         S.clear();
133         for(int i=0;i<N;i++) b[i]=1;
134         for(int i=0;i<cnt;i++){
135             LL p=pri[i];
136             if (S.count(p)) continue;
137             find_max_exp(p);
138             S.insert(p);
139         }
140         for(int i=0;i<N;i++) if (i==N-1) printf("%lld
",b[i]);else printf("%lld ",b[i]);
141     }
142     return 0;
143 }
View Code