### Loserinlife's blog

By Loserinlife, history, 4 months ago, Choose k elements from an array so that their GCD is maximise.

Constraints: N <= 3000 K <= N; K <= 100 Ai <= 10^10 (ten to the power of 10) I tried an algorithm of enumerating all divisors of ai and find the largest divisors that exists in >= k elements but it TLE. Can somebody help? Thanks in advance. Comments (8)
 » You say, $N\le 3000$, but then you again mention that $K \le N \le 100$. Can you specify the constraints clearly?
•  » » 4 months ago, # ^ | ← Rev. 2 →   I think he/she mentions : 2 <= N <= 3000 ; 1 <= K <= 100 ; 1 <= A[i] <= 1e10.
 » Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).
 » Nice problem! Is it proposed by yourself?
•  » » No its not mine. Its from an online judge :))
 » HintFirst thing to notice is that there are not a lot of different gcd's at all. Number of possible gcds is log2(10^10).
 » 4 months ago, # | ← Rev. 6 →   I slightly modify hashlife's code and find that $6983776800$ is the number $\leq 1e10$ that has the most divisors ($2304$): Spoiler#include unsigned long long n, res, argres; int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71}; unsigned long long mul(unsigned long long a, unsigned long long b){ unsigned long long res = 0; while (b){ if (b & 1LL) res = (res + a); if (res >= n) return 0; a = (a << 1LL); b >>= 1LL; } return res; } void backtrack(int i, int lim, unsigned long long val, unsigned long long r){ if (r > res) { argres = val; res = r; } if (i == p) return; int d; unsigned long long x = val; for (d = 1; d <= lim; d++){ x = mul(x, primes[i]); if (x == 0) return; backtrack(i + 1, d, x, r * (d + 1)); } } int main(){ /* Tested for n <= 10^18 */ p = sizeof(primes) / sizeof(int); while (scanf("%llu", &n) != EOF){ res = 0; backtrack(0, 100, 1, 1); printf("Maximum number of divisors of any number less than %llu = %llu, argres==%llu\n", n, res, argres); } return 0; } The code is based on backtracing. Link to the code: The gcds of $K$ elements have to be divisors of $A_i$, so there are at most $3000*2304=6912000$ divisors. For each divisor $d$ maintains a set of indices $i$ such that $A_i$ is divisible by $d$. According to a simple counting twice method, the sum of set size is no more than $6912000$ also.You may also look for Tao's blog for the $log(n)$ mean value of $d(n)$ ($d(n)$ denotes the number of divisors of $n$). Also, there is an analytic bound for $d(n)$, however, it is not very helpful in your problem. Anyway, it can enlarge our horizon. Actually, the divisor bound is much more complicated that I initially imagine!My solution: Just go through all divisors of $a[i]$ and find the largest one that occurs in $\geq k$ numbers. Spoiler#include using namespace std; using ll = long long; #define DEBUG 1 void debug(const char* p){ #if DEBUG freopen(p, "r", stdin); #else fastio; #endif } signed main(int argc, char** argv){ debug("test1.txt"); ll n, k; cin >> n >> k; map indices; for(ll i = 1, tmp; i <= n; ++i){ cin >> tmp; for(ll j = 1; j * j <= tmp; ++j){ if(tmp%j == 0){ indices[j]++; if(tmp/j != j){ indices[tmp/j]++; } } } } ll ans = 0; for(const auto& [factor, times]: indices){ //printf("factor==%lld, times==%lld\n", factor, times); if(times >= k){ ans = max(ans, factor); } } cout << ans << "\n"; } 
•  » » Hi. Thanks for the answer. I did mention a similar approach in the post, but your comments gave me an idea. To deal with tests that have duplicates with a large number of divisors, I created another map cnt to count the number of appearances so every number we only iterate through 1 time. And it passed !! :))