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
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<cmath> #include<vector> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int mod=998244353; int mo(ll a,int p){ return a>=p?a%p:a; } inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } int cnt=168; int pri[200]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47, 53,59,61,67,71,73,79,83,89,97, 101,103,107,109,113,127,131,137,139,149, 151,157,163,167,173,179,181,191,193,197,199, 211,223,227,229,233,239,241, 251,257,263,269,271,277,281,283,293, 307,311,313,317,331,337,347,349, 353,359,367,373,379,383,389,397, 401,409,419,421,431,433,439,443,449, 457,461,463,467,479,487,491,499, 503,509,521,523,541,547, 557,563,569,571,577,587,593,599, 601,607,613,617,619,631,641,643,647, 653,659,661,673,677,683,691, 701,709,719,727,733,739,743, 751,757,761,769,773,787,797, 809,811,821,823,827,829,839, 853,857,859,863,877,881,883,887, 907,911,919,929,937,941,947, 953,967,971,977,983,991,997};
int a[50020][30]; int ct[50020][30]; int n,tmp,mx; int num[50020]; int ans[1000020]; inline int speed(int a,int b){ int cur=a,anss=1; while(b){ if(b&1) anss=anss*cur; cur=cur*cur; b>>=1; } return anss; } void dfs(int t,int cur,int anx){ if(cur==a[t][0]+1){ ans[anx]++; if(ans[anx]>1) mx=max(mx,anx); return; } for(int i=0;i<=ct[t][cur];i++){ dfs(t,cur+1,anx*speed(a[t][cur],i)); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&num[i]); } sort(num+1,num+1+n); for(int i=n;i>=1;i--){ tmp=num[i]; for(int j=1;j<=cnt;j++){ if(num[i]%pri[j]==0){ a[i][++a[i][0]]=pri[j]; } while(num[i]%pri[j]==0){ ct[i][a[i][0]]++; num[i]/=pri[j]; } } if(num[i]>1){ a[i][++a[i][0]]=num[i]; ct[i][a[i][0]]++; } if(mx>=tmp){ break; }dfs(i,1,1); } printf("%d\n",mx);
return 0; }
|