1 条题解
-
0
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
- 上传者