1 条题解

  • 0
    @ 2021-6-15 13:41:23

    C++ :

    /*
    -----------------------
    Attention!
    -----------------------
    rekons的标程有错。
    正确做法是搜索剪枝(参考solutions.pdf)。
    数据比较弱,但是没有错。
    */
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <map>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    
    using namespace std;
    
    typedef long long llint;
    typedef pair <int, int> pii;
    
    const int MAXN = 55;
    
    int n;
    llint a, b;
    
    vector<llint> getDivisors (llint x) {
      vector <llint> ret;
      for (llint i = 1; i*i <= x; ++i)
        if (x % i == 0) ret.push_back(i), ret.push_back(x / i);
      sort(ret.begin(), ret.end());
      ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
      return ret;
    }
    
    bool test(llint x, vector <llint> &V) {
      llint first;
      if (a % x != 0) first = a - a%x + x;
      else first = a;
      while (first <= b) {
        if (!binary_search(V.begin(), V.end(), first))
          return 0;
        first += x;
      }
      return 1;
    }
    
    bool uzeo[MAXN];
    int interpret (char *s) {
      while (strlen(s) != 5)
        s[strlen(s)] = '0';
      int ret = 0;
      for (int i = 0; i < 5; ++i)
        ret = ret * 10 + s[i] - '0';
      return ret;
    }
    
    int main (void){
     // freopen("rekons.in", "r", stdin);
     // freopen("rekons.out", "w", stdout);
      scanf("%d", &n);
      scanf("%lld%lld", &a, &b);
      a *= 100000;
      b *= 100000;
      vector <llint> V;
      for (int i = 0; i < n; ++i) {
        int x;
        char y[10] = {0};
        int cnt = scanf("%d.%s\n", &x, y);
        if (cnt == 1) y[0] = 0;
        llint broj = (llint)x * 100000 + interpret(y);
        V.push_back(broj);
      }
      sort(V.begin(), V.end());
      vector <llint> ans;
      for (int i = 0; i < n; ++i) {
        vector<llint> divisors = getDivisors(V[i]);
        if (uzeo[i] == 1) continue;
        for (int k = 0; k < divisors.size(); k ++)
          if (test(divisors[k], V)) {
    	for (int j = i; j < n; ++j)
    	  if (V[j] % divisors[k] == 0) uzeo[j] = 1;
    	ans.push_back(divisors[k]);
    	break;
          }
      }
      for (int i = 0; i < ans.size(); i ++)
        printf("%lld.%05lld\n", ans[i] / 100000, ans[i] % 100000);
      
      return 0;
    }
    
    
    • 1

    信息

    ID
    949
    时间
    2000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者