ACM模版

描述

题解

遇见这种问题,我一般都是直接模拟。

先考虑到,能保证他一定会返回起点的扔法只有朝将圆 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;
}

参考

《欧拉函数PHI》