HDU-1286-找新朋友

描述

题解

很显然是欧拉函数的裸题，当然，这个题是我用来测试自己欧拉函数几个模版的。

测试代码

One：分解质因数法

// AC 模版通过
#include <iostream>
#include <cstring>

using namespace std;

/* * 合数的分解需要先进行素数的筛选 * factor[i][0]存放分解的素数 * factor[i][1]存放对应素数出现的次数 * fatCnt存放合数分解出的素数个数(相同的素数只算一次) */

const int MAXN = 40000 + 10;

int n;
int prime[MAXN + 1];

// 获取素数
void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= MAXN; i++)
    {
        if (!prime[i])
        {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++)
        {
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0)
            {
                break;
            }
        }
    }
    return ;
}

long long factor[100][2];
int fatCnt;

// 合数分解
int getFactors(long long x)
{
    fatCnt = 0;
    long long tmp = x;
    for (int i = 1; prime[i] <= tmp / prime[i]; i++)
    {
        factor[fatCnt][1] = 0;
        if (tmp % prime[i] == 0)
        {
            factor[fatCnt][0] = prime[i];
            while (tmp % prime[i] == 0)
            {
                factor[fatCnt][1]++;
                tmp /= prime[i];
            }
            fatCnt++;
        }
    }
    if (tmp != 1)
    {
        factor[fatCnt][0] = tmp;
        factor[fatCnt++][1] = 1;
    }
    return fatCnt;
}

/* * 分解质因数法求解，getFactor(n)函数见《合数相关》 */
int main(int argc, const char * argv[])
{
    getPrime();

    int T;
    cin >> T;

    while (T--)
    {
        cin >> n;
        getFactors(n);
        int ret = n;
        for (int i = 0; i < fatCnt; i++)
        {
            ret = (int)(ret / factor[i][0] * (factor[i][0] - 1));
        }

        cout << ret << '\n';
    }

    return 0;
}

Two：筛法欧拉函数

// AC 模版通过
#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 40000;

int n;
int phi[MAXN + 2];

int main(int argc, const char * argv[])
{
    for (int i = 1; i <= MAXN; i++)
    {
        phi[i] = i;
    }
    for (int i = 2; i <= MAXN; i += 2)
    {
        phi[i] /= 2;
    }
    for (int i = 3; i <= MAXN; i += 2)
    {
        if (phi[i] == i)
        {
            for (int j = i; j <= MAXN; j += i)
            {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }

    int T;
    cin >> T;

    while (T--)
    {
        cin >> n;
        cout << phi[n] << '\n';
    }

    return 0;
}

Three：单独求解

// AC 模版通过
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int n;

/* * 单独求解的本质是公式的应用 */
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 T;
    cin >> T;

    while (T--)
    {
        cin >> n;
        cout << euler(n) << '\n';
    }

    return 0;
}

four：线性筛

// AC 模版通过
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int n;

/* * 同时得到欧拉函数和素数表 */
const int MAXN = 40000;

bool check[MAXN + 10];
int phi[MAXN + 10];
int prime[MAXN + 10];
int tot;    // 素数个数

void phi_and_prime_table(int N)
{
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
            if (i * prime[j] > N)
            {
                break;
            }
            check[i * prime[j]] = true;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else
            {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
    return ;
}

int main(int argc, const char * argv[])
{
    phi_and_prime_table(MAXN);

    int T;
    cin >> T;

    while (T--)
    {
        cin >> n;
        cout << phi[n] << '\n';
    }

    return 0;
}

模版测试结果

四种模版测试结果均无逻辑错误或者其他错误。