Codeforces Round 868 (Div. 2) 1823C. Strongly Composite Solution

 

Problem Link : https://codeforces.com/problemset/problem/1823/C

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int32_t main() {
5. ios_base::sync_with_stdio(0);
6. cin.tie(0);
7. int t;
8. cin >> t;
9. while (t--) {
10. int n ;
11. cin >> n ;
12. map<int,int>mp ;
13. for ( int k = 0 ; k < n ; k++){
14. int x ;
15. cin >> x ;
16. for ( int i = 2 ; i * i <= x ; i++){
17. if (x % i == 0){
18. while ( x % i == 0){
19. x /= i ;
20. mp[i]++;
21. }
22. }
23. }
24. if ( x > 1 ){
25. mp[x]++ ;
26. }
27. }
28. int ans = 0 , cnt = 0 ;
29. for ( auto i : mp){
30. ans += (i.second / 2) ;
31. cnt += (i.second % 2) ;
32. }
33. ans += (cnt / 3) ;
34. cout << ans <<'\n' ;
35. }
36. return 0 ;
37. }