题目

{% raw %}

点击显/隐题目
{% endraw %} 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, ,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at yth position which satisfy

x mod y=0

Is there any way to satisfy everyone's requirement
{% raw %}



{% endraw %}
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≤T≤100.
1≤n≤109.
0≤s≤109.
{% raw %}



{% endraw %}
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'.
{% raw %}





{% endraw %}
2
5 14
4 11
{% raw %}


{% endraw %}
Case #1: No
Case #2: Yes

{% raw %}




{% endraw %} # 题解 题意比较容易理解,对于 `[s+1,s+n]` 这 `n` 个人,将他们放置在 `[1,n]` 这些位置上 其中 编号为 `x` 的人 只能放在位置 `y` 上,有 `x mod y = 0`

按照样例自己在纸上花出来,可以发现就是 二分图匹配
对于一组数据判断是否能够做到 最佳完美匹配

看数据量可以发现数据高达 109
然而,根据经验可知,随着数的增大,两个素数之间的距离会变大,但对于 109 的数据量,间距仍然是一个确定的值
当需要运算的区间 有多个素数时,显然可以直接输出 "No"
(都要放在 1 的位置上)

因此,一个比较可行的思路是先判断下是否有多个素数,如果有可能有解的情况下,使用 匈牙利算法 进行计算

关于判断是否有多个思路,有两种思路:

  1. 对于一组数据的每一个数据都进行判断是否为素数,当找到 2 个以上时,直接跳出循环
  2. 找到 109 素数间隔的最大值,只在小于时计算

首先假设最大的间隔为 Max
对于第一种思路,采用 费马小定理 每次判断的时间复杂度为 log(n)^2
一组数据最坏要查询 Max 次
而直接判断显然可以忽略这个时间

而由于匈牙利算法的时间复杂度为 O(nm)

显然,只有 Max 较大的情况下,方案 1 更好
(已经可以预知,不管怎么样,如果方案 2 都超时,方案 1 必定超时)

根据查表, 109 的素数最大间隔还不到 300

因此大于 300 直接输出 "No" 即可
对于小于 300 的情况直接使用是匈牙利算法即可

有一点需要特别注意: [s+1,s+n] 和 [1,n] 有可能存在重合区间
对于重合部分,无论有多少素数,都没关系(自己对自己取余为 0 )

因此,二分图处理的部分应该是不重合的部分(找因子的时候,直接使用本身比使用它的一个因子更“划算”)
假设有重合区域,则重合区域应该为 [s+1,n]
因此应该对 [1,s+1) 和 (n,s+n] 区域求二分图匹配
也即对 [1,s] 和 [n+1,n+s] 区域求二分图匹配,恰好就是交换 s 和 n
也就是说,当 n>=s+1 (s<n) 时交换两者,就可以避过重合问题
(当然,通过其他的判断也可以解决)

代码

点击显/隐代码
```cpp Kingdom of Obsession https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /* #define debug #include //*/

#include
#include
#include
#include
#include
using namespace std;

typedef long long LL;

/*

  • 匈牙利算法邻接表形式
  • 使用前用init()进行初始化，给uN赋值
  • 加边使用函数addedge(u,v)
    /
    const int MAXN = 2005;//点数的最大值
    const int MAXM = MAXN    MAXN;//边数的最大值
    struct Edge {
    int to,next;
    }edge[MAXM];

int head[MAXN],tot,uN;
void init(int un) {
uN = un;
tot = 0;
memset(head,-1,sizeof(head));
}

void addedge(int u,int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}

int linker[MAXN];
bool used[MAXN];
bool dfs(int u) {
for(int i = head[u]; i != -1;i = edge[i].next){
int v = edge[i].to;
if(!used[v]){
used[v] = true;
if(linker[v] == -1 || dfs(linker[v])){
linker[v] = u;
return true;
}
}
}
return false;
}
int hungary(){
int res = 0;
memset(linker,-1,sizeof(linker));
for(int u = 0; u < uN;u++){//点的编号0~uN-1
memset(used,false,sizeof(used));
if(dfs(u))
res++;
}
return res;
}

bool Solve(int n,int s){
if(s<n) swap(s,n);
if(n>1000) return false;

//匈牙利算法 求解二分图
init(n);
for(int i=1;i<=n;i++){
    LL t = (LL)i+(LL)s;
    for(int j=1;j<=n;j++){
        if(t%j==0)
            addedge(j-1,i-1);
    }
}
//cout<<hungary()<<endl;
return hungary()==n;

}

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif

int T;
cin>>T;
for(int kase=1;kase<=T;kase++){
    int n,s;
    cin>>n>>s;
    cout<<"Case #"<<kase<<": "<<(Solve(n,s)?"Yes":"No")<<endl;
}

#ifdef debug
printf("Time:%.3lfs\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div></div>