学步园

       欧拉函数好题。题意：给你一个数m，请你输出从1开始升序排列与m互素的数列中的第k个数。

       我的解题思路：根据数据范围，K最大可以达到1E，比m还大，因此很容易想到数据会超过32位整型。而且要找m的第k个与m互素的数肯定不能用暴力枚举的办法。

两个互素的数a，b它们满足gcd(a,b) = 1这个条件，根据gcd的这么一个性质gcd(a,b) = gcd(b,a%b)即gcd(a,b) = gcd(b, a + nb)，其中n可以为任意非负整数。从这里我们可以发现一个规律那就是与b互质的数是有周期规律的，如果第一个周期与b互素的数列为[1, ... , x]（x <= b），那么第二个周期与b互素的数列就是[1 + b, ... , x + b]，第三个周期就是[1 + 2b, ...,
x + 2b]，因此我们可以通过算出小于等于b与b互素的数列来推出所有与b互素的数了。

运用到这道题上，先求出小于等于m与m互素的数以及它们的个数即m的欧拉函数值，然后就可以算出第k个与m互素的数在第几个周期上，从而算出对应的数。

       我的解题代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long Long;

const Long N = 1000001;

bool m_prime[N];    //判断是否与m互素
Long m, k;

void DataProcess();

Long Phi(Long x);   //计算欧拉函数的同时标记不与m互素的数

int main()
{
    while (~scanf("%lld %lld", &m, &k))
    {
        DataProcess();
    }
    return 0;
}

void DataProcess()
{
    memset(m_prime, true, sizeof(m_prime));
    Long n = Phi(m);
    Long cnt = 0;
    Long key = k % n == 0 ? n : k % n;
    Long tmp = (k - 1) / n;     //计算周期
    for (Long i=1; i<=m; ++i)
    {
        if (m_prime[i] && ++cnt == key)
        {
            printf("%lld\n", i + tmp * m);
            break;
        }
    }
    return;
}

Long Phi(Long x)
{
    Long ans = x;
    Long cnt = (Long)sqrt(x + 0.5) + 1;
    for (Long i=2; i<cnt; ++i)
    {
        if (x % i == 0)
        {
            ans -= ans / i;
            while (x % i == 0) x /= i;
            for (Long j=i; j<N; j+=i) m_prime[j] = false;
        }
    }
    if (x > 1)
    {
        ans -= ans / x;
        for (Long j=x; j<N; j+=x) m_prime[j] = false;
    }
    return ans;
}