SRM406 Div2 Medium

500

やるだけ

view plainprint?

1. class FactoVisors {  
2. public:  
3.   int getNum(vector <int> D, vector <int> M)  
4.   {  
5.     set<lli> ns[M.size()];  
6.     for (int i = 0; i < (int)M.size(); ++i) {  
7.       for (lli j = 1; j * j <= M[i]; ++j) {         
8.         if (M[i] % j == 0) {  
9.           ns[i].insert(j);  
10.           ns[i].insert(M[i] / j);  
11.         }  
12.       }  
13.     }  
14.   
15.     set<lli> cand;  
16.   
17.     FOR (i, ns[0]) {  
18.       bool flg = true;  
19.       for (int j = 0; j < (int)M.size(); ++j) {  
20.         flg = flg && ns[j].count(*i);  
21.       }  
22.       if (flg) cand.insert(*i);  
23.     }  
24.   
25.     int ret = 0;  
26.   
27.     FOR (i, cand) {  
28.       bool flg = true;  
29.       for (int j = 0; j < (int)D.size(); ++j) {  
30.         flg = flg && *i % D[j] == 0;  
31.       }  
32.       ret += flg;  
33.     }  
34.   
35.     return ret;  
36.   }  
37. };  

class FactoVisors {
public:
  int getNum(vector <int> D, vector <int> M)
  {
    set<lli> ns[M.size()];
    for (int i = 0; i < (int)M.size(); ++i) {
      for (lli j = 1; j * j <= M[i]; ++j) {       
        if (M[i] % j == 0) {
          ns[i].insert(j);
          ns[i].insert(M[i] / j);
        }
      }
    }

    set<lli> cand;

    FOR (i, ns[0]) {
      bool flg = true;
      for (int j = 0; j < (int)M.size(); ++j) {
        flg = flg && ns[j].count(*i);
      }
      if (flg) cand.insert(*i);
    }

    int ret = 0;

    FOR (i, cand) {
      bool flg = true;
      for (int j = 0; j < (int)D.size(); ++j) {
        flg = flg && *i % D[j] == 0;
      }
      ret += flg;
    }

    return ret;
  }
};