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. }

No comments

Most View Post

Recent post

Codeforces Round 971 (Div. 4) 2009C. The Legend of Freya the Frog Solution

  Problem Link    https://codeforces.com/contest/2009/problem/C S olution in C++: /// Author : AH_Tonmoy #include < bits / stdc ++. h ...

Powered by Blogger.