A - Enlarge GCD || Codeforces Round #511 (Div. 1)

 প্রব্লেম স্টেটমেন্টঃ একটা এরে দেয়া হবে। মিনিমাম কতগুলো ভ্যালু রিমোভ করলে এর জিসিডি সবগুলো ভ্যালুর জিসিডি থেকে বেশি হবে।

অবজারবেশণঃ ব্রুটফুরস করে পব্লেম টি সল্ভ করা সম্ভব নয়। এখানে আমরা প্রথমে সবগুলো নাম্বারের জিসডি বের করে নিব।

এপরপর সবগুলো নাম্বার কে  জিসিডি দিয়ে ভাগ করব। যার ফলে সবগুলো সংখ্যা থেকে জিসিডি বাদ হয়ে যাবে।(জিসিডি মানে সব থেকে বড় কমন ডিভিজর) 

আমরা জানি, প্রত্যেক টি সংখ্যাকে নির্দিষ্ট সংখ্যক প্রাইমের প্রডাক্ট হিসেবে প্রকাশ করা যায়। সুতরাং সবগুলো সংখ্যার প্রাইম জেনারেট করে দেখতে হবে কোন প্রাইম টি সর্বোচ্চ সংখ্যক নাম্বারের ভিতর আছে। এরপর নরমালি N থেকে, যে প্রাইমটি সর্বোচ্চ সংখ্যক নাম্বারের ভিতর আছে সেটি বিয়োগ দিলেই আন্সার পেয়ে যাবো।

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define ll long long
4. const ll N = 15000005;
5. ll spf[N+1];
6. void cspf(){
7. for(ll i = 2; i <= 15000000; ++i) spf[i] = i;
8. for(ll i = 2; i <= 15000000; i++){
9. if(spf[i] == i){
10. for(ll j = i*i*1LL; j <= 15000000; j += i){
11. spf[j] = min(i,spf[j]);
12. }
13. }
14. }
15. }
16. int32_t main(){
17. ios_base::sync_with_stdio(false);cin.tie(NULL);
18. cspf();
19. ll n; cin >> n;
20. vector<ll>v(n);
21. ll g = 0;
22. for(ll i = 0; i < n; ++i){
23. cin >> v[i];
24. g = __gcd(g, v[i]);
25. }
26. //cout << g << '\n';
27. for(ll i = 0; i < n; ++i) v[i] /= g;
28. map<ll,ll>MAP;
29. for(ll i = 0; i < n; ++i){
30. while(v[i] > 1){
31. ll p = spf[v[i]];
32. MAP[p]++;
33. while(v[i] % p == 0){
34. v[i]/=p;
35. }
36. }
37. }
38. ll ans = 0;
39. for(auto it: MAP){
40. ans = max(ans,it.second);
41. }
42. if(ans == 0) cout << -1 << '\n';
43. else cout << n - ans << '\n';
44.  
45. }