yukicoder-382
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
display: block;
padding: 9.5px;
margin: 0 0 10px;
font-size: 13px;
line-height: 1.42857143;
color: #333;
word-break: break-all;
word-wrap: break-word;
background-color: #f5f5f5;
border: 1px solid #ccc;
border-radius: 4px;
}
</style>
}}}
== [https://yukicoder.me/problems/no/382 No.382 シャイな人たち (2)] ==
=== Description ===
{{{
#!html
<p>有$N$个人参加比赛，第$i$个人和第$j$个人之间的友好度是$F_{ij}=F_{ji}$。对于给定的一个值$P$，你需要找到一个最小的$k$，使得对于任意$k$个人，都能找到$2$个人的友好度大于等于$P$。</p>
<p>数据是随机生成的，对于一个给定的参数$S$，会按照下面代码生成数据：</p>
<p class='input'>
$S$ is given<br>
$S=(S \times 12345) \bmod 1000003$<br>
$N=(S \bmod 120) + 2$<br>
$S=(S \times 12345) \bmod 1000003$<br>
$P=S$<br>
for ($i$ = 1; $i$ <= $N$; $i$++) {<br>
for ($j$=$i$ + 1; $j$ <= $N$; $j$++) {<br>
$S=(S\times 12345)\bmod 1000003$<br>
$F_{ij}=F_{ji}=S$<br>
}<br>
}
</p>
}}}
=== Input ===
{{{
#!html
<p class="input">$S$</p>
<p>
$1 \le S < 1000003$</p>
}}}
=== Output ===
{{{
#!html
<p>第一行输出满足条件的最小的$k$，如果不存在输出$-1$。如果存在，在第二行输出$k-1$个整数，要求这$k-1$个人任意两人的友好度小于$P$。</p>
}}}
=== Sample ===
==== Sample 1 ====
输入
{{{
#!html
<pre>
657
</pre>
}}}
输出
{{{
#!html
<pre>
3
1 3
</pre>
}}}
==== Sample 2 ====
输入
{{{
#!html
<pre>
58
</pre>
}}}
输出
{{{
#!html
<pre>
5
87 86 12 44
</pre>
}}}
==== Sample 3 ====
输入
{{{
#!html
<pre>
31884
</pre>
}}}
输出
{{{
#!html
<pre>
37
7 36 70 79 6 35 14 78 15 59 68 56 16 46 69 28 54 81 83 8 34 53 1 24 32 13 17 66 19 38 12 18 23 41 73 40
</pre>
}}}No.382 シャイな人たち (2)
Description
有$N$个人参加比赛，第$i$个人和第$j$个人之间的友好度是$F_{ij}=F_{ji}$。对于给定的一个值$P$，你需要找到一个最小的$k$，使得对于任意$k$个人，都能找到$2$个人的友好度大于等于$P$。
数据是随机生成的，对于一个给定的参数$S$，会按照下面代码生成数据：
$S$ is given
$S=(S \times 12345) \bmod 1000003$
$N=(S \bmod 120) + 2$
$S=(S \times 12345) \bmod 1000003$
$P=S$
for ($i$ = 1; $i$ <= $N$; $i$++) {
for ($j$=$i$ + 1; $j$ <= $N$; $j$++) {
$S=(S\times 12345)\bmod 1000003$
$F_{ij}=F_{ji}=S$
}
}
Input
$S$
$1 \le S < 1000003$
Output
第一行输出满足条件的最小的$k$，如果不存在输出$-1$。如果存在，在第二行输出$k-1$个整数，要求这$k-1$个人任意两人的友好度小于$P$。
Sample
Sample 1
输入
657
输出
31 3
Sample 2
输入
58
输出
587 86 12 44
Sample 3
输入
31884
输出
377 36 70 79 6 35 14 78 15 59 68 56 16 46 69 28 54 81 83 8 34 53 1 24 32 13 17 66 19 38 12 18 23 41 73 40