描述
题解
遇见这种问题,我一般都是直接模拟。
先考虑到,能保证他一定会返回起点的扔法只有朝将圆 N + 1 等分的 N 个点(起点不算)扔去,但是有的跨度无法满足弹 N 次的要求。
于是我从1一直画到了7的情况,然后感觉扔出去的每一步的跨度不能被 N + 1 整除,如果整除就一定无法弹 N 次,结果写好代码后,先是 WA 了几组,然后是 TLE 了。
所以我推断,应该是我的这个条件还是比较弱,并且没有真正的利用其规律,如果条件找得足够强应该可以发现数学性更强的公式或者神马数论,然后我又想了想,会不会连公因子(除1外)也不能有呢?也就是说是否跨度必须与 N + 1 互素呢?如果是这样,那么这个问题也就是说要求 N + 1 的欧拉函数了。于是我找了一种状态试了试,当 N = 23,跨度为 9 时,gcd(24, 9) = 3,结果果然无法弹 N 次!GG~~~
那么,直接上模版喽,效率十分快的哦~~~
代码
#include <iostream>
#include <cmath>
using namespace std;
/* * 单独求解的本质是公式的应用 */
unsigned euler(unsigned x)
{
unsigned i, res = x; // unsigned == unsigned int
for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
{
if (!(x % i))
{
res = res / i * (i - 1);
while (!(x % i))
{
x /= i; // 保证i一定是素数
}
}
}
if (x > 1)
{
res = res / x * (x - 1);
}
return res;
}
int main(int argc, const char * argv[])
{
int N;
while (cin >> N)
{
if (N == 1)
{
printf("1\n");
continue;
}
N++;
int res = euler(N);
printf("%d\n", res);
}
return 0;
}