http://acm.hdu.edu.cn/showproblem.php?pid=5943
Kingdom of Obsession
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there are $n$ people with their id continuous $(s+1, s+2, \cdots, s+n)$ standing in a line in arbitrary order, be more obsessively, people with id $x$ wants to stand at $y^{th}$ position which satisfy
$$x \mod y = 0$$
Is there any way to satisfy everyone's requirement?
They name themselves in integer, and there are $n$ people with their id continuous $(s+1, s+2, \cdots, s+n)$ standing in a line in arbitrary order, be more obsessively, people with id $x$ wants to stand at $y^{th}$ position which satisfy
$$x \mod y = 0$$
Is there any way to satisfy everyone's requirement?
Input
First line contains an integer $T$, which indicates the number of test cases.
Every test case contains one line with two integers $n$, $s$.
Limits
$1 \leq T \leq 100$.
$1 \leq n \leq 10^9$.
$0 \leq s \leq 10^9$.
Every test case contains one line with two integers $n$, $s$.
Limits
$1 \leq T \leq 100$.
$1 \leq n \leq 10^9$.
$0 \leq s \leq 10^9$.
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.
If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.
If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.
Sample Input
2
5 14
4 11
Sample Output
Case #1: No
Case #2: Yes
Source
题意:
有n个人,分别id为s+1,s+2,……s+n,现在让这n个人排队,要求每个位置的人的id要能被位置号整除,问是否可行。
思路:
考虑到id为质数的人,只能被放到第一个位置,或者放到位置号和他id相同的位置。当s+1……s+n区间内出现2个质数以上质数的时候,一定要将后部分放到前面去。因为数据范围为$1 \leq n \leq 10^9$.$0 \leq s \leq 10^9$.这个范围下相邻的两个质数都靠的比较近,可以暴力从s+n开始往前,验证区间的质数是否大于等于2。
如果区间内的质数小于2个,则将s+1到s+n的数与1到n进行二分匹配。
如果区间内的质数大于等于2个,则将后s个数与1到s进行二分匹配。
如果完全匹配上就是可行的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 2510; const LL maxm = 1000010; LL cnt, p[maxn]; struct node { LL v, next; } E[maxm]; LL n, m; void init() { cnt = 0; memset(p, -1, sizeof(p)); } void add(LL u, LL v) { E[cnt].v = v; E[cnt].next = p[u]; p[u] = cnt++; } LL fg[maxn]; LL pp[maxn]; bool Find(LL x) { for (LL i = p[x]; i != -1; i = E[i].next) { LL y = E[i].v; if (!fg[y]) { fg[y] = 1; if (pp[y] == 0 || Find(pp[y])) { pp[y] = x; return 1; } } } return 0; } LL solve() { LL ans = 0; for (LL i = 1; i <= n; i++) pp[i] = 0; for (LL i = 1; i <= n; i++) { for (LL j = 1; j <= n; j++) fg[j] = 0; if (Find(i)) ans++; } return ans; } bool isprime(LL x) { for (LL i = 2; i * i <= x; i++) if (x % i == 0) return 0; return 1; } int main() { LL T, ks = 0; scanf("%lld", &T); while (T--) { init(); LL N; LL x, y; scanf("%lld %lld", &y, &x); printf("Case #%lld: ", ++ks); N = y; y += x; x++; LL cntx = 0; LL p1, p2; for (LL i = y; i >= x; i--) { if (isprime(i)) { cntx++; if (cntx == 1) p2 = i; else { p1 = i; break; } } } if (cntx <= 1) { for (LL i = x; i <= y; i++) { for (LL j = 1; j * j <= i && j <= N; j++) if (i % j == 0) { add(i - x + 1, j); if (i / j <= N && j * j != i) add(i - x + 1, i / j); } } n = N; LL ans = solve(); if (ans == n) puts("Yes"); else puts("No"); } else { LL need = x - 1; if (y - p1 < need) { puts("No"); continue; } LL st = y - need + 1; for (LL i = st; i <= y; i++) { for (LL j = 1; j * j <= i && j <= need; j++) if (i % j == 0) { add(i - st + 1, j); if (i / j <= need && j * j != i) add(i - st + 1, i / j); } } n = need; LL ans = solve(); if (ans == n) puts("Yes"); else puts("No"); } } return 0; } |