【补题】18年多校3

目录

• Euler Function [HDU 6322]
• Grab The Tree [HDU 6324]

---

Euler Function

Description

Giving an integer $k$, your task is to find the $k-th$ smallest positive integer $n$, that $\phi(n)$ is a composite number.

Solution

由$gcd(n,\ k)=gcd(n,\ n-k)$，易得$n>2$时$\phi(n)$为偶数，则不难证明当$n\le 7$时，$\phi(n)$恒为合数。

#include <cstdio>

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int k;
        scanf("%d", &k);
        printf("%d\n", k == 1 ? 5 : 5 + k);
    }
    return 0;
}

Grab The Tree

Description

Giving an integer $k$, your task is to find the $k-th$ smallest positive integer $n$, that $\phi(n)$ is a composite number.

Solution

由$gcd(n,\ k)=gcd(n,\ n-k)$，易得$n>2$时$\phi(n)$为偶数，则不难证明当$n\le 7$时，$\phi(n)$恒为合数。

#include <cstdio>

int main()
{
    int T;
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++)
    {
        int k;
        scanf("%d", &k);
        printf("%d\n", k == 1 ? 5 : 5 + k);
    }
    return 0;
}