<h1 id="heading">题目</h1>
<p>{% raw %}</p>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐题目</div></div><div class="fold">
    <div class="oj">   
        <div class="part" title="Description">
{% endraw %}
There is a kindom of obsession, so people in this kingdom do things very strictly.  
<p>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</p>
<p><code>x mod y=0</code></p>
<p>Is there any way to satisfy everyone's requirement<br>
{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}<br>
First line contains an integer T, which indicates the number of test cases.</p>
<p>Every test case contains one line with two integers n, s.</p>
<p>Limits</p>
<blockquote>
<p>1≤T≤100.<br>
1≤n≤109.<br>
0≤s≤109.<br>
{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}<br>
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.</p>
</blockquote>
<p>If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'. <br>
{% raw %}<br>
</div><br>
<div class="samp"><br>
<div class="clear"></div><br>
<div class="input part" title="Sample Input"><br>
{% endraw %}<br>
2<br>
5 14<br>
4 11<br>
{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}<br>
Case #1: No<br>
Case #2: Yes</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

# 题解
题意比较容易理解,对于 `[s+1,s+n]` 这 `n` 个人,将他们放置在 `[1,n]` 这些位置上  
其中 编号为 `x` 的人 只能放在位置 `y` 上,有 `x mod y = 0`  
<p>按照样例自己在纸上花出来,可以发现就是 <strong>二分图匹配</strong><br>
对于一组数据判断是否能够做到 <strong>最佳完美匹配</strong></p>
<p>看数据量可以发现数据高达 <code>10<sup>9</sup></code><br>
然而,根据经验可知,随着数的增大,两个素数之间的距离会变大,但对于 <code>10<sup>9</sup></code> 的数据量,间距仍然是一个确定的值<br>
当需要运算的区间 <strong>有多个素数时,显然可以直接输出 &quot;No&quot;</strong><br>
(都要放在 <code>1</code> 的位置上)</p>
<p>因此,一个比较可行的思路是先判断下是否有多个素数,如果有可能有解的情况下,使用 <strong>匈牙利算法</strong> 进行计算</p>
<p>关于判断是否有多个思路,有两种思路:</p>
<ol>
<li>对于一组数据的每一个数据都进行判断是否为素数,当找到 2 个以上时,直接跳出循环</li>
<li>找到 <code>10<sup>9</sup></code> 素数间隔的最大值,只在小于时计算</li>
</ol>
<p>首先假设最大的间隔为 Max<br>
对于第一种思路,采用 <strong>费马小定理</strong> 每次判断的时间复杂度为 log(n)^2<br>
一组数据最坏要查询 Max 次<br>
而直接判断显然可以忽略这个时间</p>
<p>而由于匈牙利算法的时间复杂度为 O(nm)</p>
<p>显然,只有 Max 较大的情况下,方案 1 更好<br>
(已经可以预知,不管怎么样,如果方案 2 都超时,方案 1 必定超时)</p>
<p>根据查表, <code>10<sup>9</sup></code> 的素数最大间隔还不到 300</p>
<p>因此大于 300 直接输出 &quot;No&quot; 即可<br>
对于小于 300 的情况直接使用是匈牙利算法即可</p>
<p><strong>有一点需要特别注意: <code>[s+1,s+n]</code> 和 <code>[1,n]</code> 有可能存在重合区间</strong><br>
对于重合部分,无论有多少素数,都没关系(自己对自己取余为 0 )</p>
<p>因此,二分图处理的部分应该是不重合的部分(找因子的时候,直接使用本身比使用它的一个因子更“划算”)<br>
假设有重合区域,则重合区域应该为 <code>[s+1,n]</code><br>
因此应该对 <code>[1,s+1)</code> 和 <code>(n,s+n]</code> 区域求二分图匹配<br>
也即对 <code>[1,s]</code> 和 <code>[n+1,n+s]</code> 区域求二分图匹配,恰好就是交换 <code>s</code> 和 <code>n</code><br>
也就是说,当 <code>n&gt;=s+1</code> (<code>s&lt;n</code>) 时交换两者,就可以避过重合问题<br>
(当然,通过其他的判断也可以解决)</p>
<h1 id="heading-1">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp Kingdom of Obsession https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*
#define debug
#include <ctime>
//*/
<p>#include <cstdio><br>
#include <iostream><br>
#include <cstring><br>
#include <cmath><br>
#include <cstdlib><br>
using namespace std;</p>
<p>typedef long long LL;</p>
<p>/*</p>
<ul>
<li>匈牙利算法邻接表形式</li>
<li>使用前用init()进行初始化，给uN赋值</li>
<li>加边使用函数addedge(u,v)<br>
<em>/<br>
const int MAXN = 2005;//点数的最大值<br>
const int MAXM = MAXN</em>MAXN;//边数的最大值<br>
struct Edge {<br>
int to,next;<br>
}edge[MAXM];</li>
</ul>
<p>int head[MAXN],tot,uN;<br>
void init(int un) {<br>
uN = un;<br>
tot = 0;  <br>
memset(head,-1,sizeof(head));<br>
}</p>
<p>void addedge(int u,int v) {<br>
edge[tot].to = v;<br>
edge[tot].next = head[u];  <br>
head[u] = tot++;<br>
}</p>
<p>int linker[MAXN];<br>
bool used[MAXN];<br>
bool dfs(int u) {  <br>
for(int i = head[u]; i != -1;i = edge[i].next){<br>
int v = edge[i].to;<br>
if(!used[v]){<br>
used[v] = true;<br>
if(linker[v] == -1 || dfs(linker[v])){<br>
linker[v] = u;<br>
return true;<br>
}<br>
}<br>
}<br>
return false;<br>
}<br>
int hungary(){<br>
int res = 0;<br>
memset(linker,-1,sizeof(linker));<br>
for(int u = 0; u &lt; uN;u++){//点的编号0~uN-1<br>
memset(used,false,sizeof(used));<br>
if(dfs(u))<br>
res++;<br>
}<br>
return res;<br>
}</p>
<p>bool Solve(int n,int s){<br>
if(s&lt;n) swap(s,n);<br>
if(n&gt;1000) return false;</p>
<pre><code>//匈牙利算法 求解二分图
init(n);
for(int i=1;i&lt;=n;i++){
    LL t = (LL)i+(LL)s;
    for(int j=1;j&lt;=n;j++){
        if(t%j==0)
            addedge(j-1,i-1);
    }
}
//cout&lt;&lt;hungary()&lt;&lt;endl;
return hungary()==n;
</code></pre>
<p>}</p>
<p>int main(){<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif</p>
<pre><code>int T;
cin&gt;&gt;T;
for(int kase=1;kase&lt;=T;kase++){
    int n,s;
    cin&gt;&gt;n&gt;&gt;s;
    cout&lt;&lt;&quot;Case #&quot;&lt;&lt;kase&lt;&lt;&quot;: &quot;&lt;&lt;(Solve(n,s)?&quot;Yes&quot;:&quot;No&quot;)&lt;&lt;endl;
}

#ifdef debug
printf(&quot;Time:%.3lfs\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">&lt;/div&gt;&lt;/div&gt;</pre>

HDU 5943.Kingdom of Obsession(2016 CCPC 杭州 K)