Advertisement
Josif_tepe

Untitled

Dec 30th, 2022
1,042
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <cmath>
  5. using namespace std;
  6. const int maxn = 200;
  7. typedef long long ll;
  8. int graph[maxn][maxn];
  9. int n;
  10. ll gcd(ll a, ll b) {
  11.     if(a < b) {
  12.         swap(a, b);
  13.     }
  14.     while(b > 0) {
  15.         ll tmp = a;
  16.         a = b;
  17.         b = tmp % b;
  18.     }
  19.     return a;
  20. }
  21. bool check_perfect_square(ll a, ll b) {
  22.     ll c = (a * a) + (b * b);
  23.     ll sq = sqrt(c);
  24.     if(sq * sq == c) {
  25.         return true;
  26.     }
  27.     return false;
  28. }
  29. bool visited[maxn];
  30. int match[maxn];
  31. bool dfs(int node) {
  32.     for(int i = 0; i < maxn; i++) {
  33.         if(graph[node][i] and !visited[i]) {
  34.             visited[i] = true;
  35.             if(match[i] == -1 or dfs(match[i])) {
  36.                 match[i] = node;
  37.                 return true;
  38.             }
  39.         }
  40.     }
  41.     return false;
  42. }
  43. int maximum_bipartite_matching() {
  44.     memset(match, -1, sizeof match);
  45.     int result = 0;
  46.     for(int i = 0; i < maxn; i++) {
  47.         memset(visited, false, sizeof visited);
  48.         if(dfs(i)) {
  49.             result++;
  50.         }
  51.     }
  52.     return result;
  53. }
  54. int main() {
  55.     cin >> n;
  56.     vector<ll> v(n);
  57.     for(int i = 0; i < n; i++) {
  58.         cin >> v[i];
  59.     }
  60.    
  61.     for(int i = 0; i < n; i++) {
  62.         for(int j = 0; j < n; j++) {
  63.             if(gcd(v[i], v[j]) == 1 and check_perfect_square(v[i], v[j])) {
  64.                 graph[i][j] = 1;
  65.             }
  66.         }
  67.     }
  68.     cout << maximum_bipartite_matching() << endl;
  69.     return 0;
  70. }
  71.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement