[HDU - 3501] Calculation 2

这篇文章以后的更新都会在 https://two-plus-two-make-four.blogspot.com/2020/01/hdu-3501-calculation-2.html

题意

给你一个正整数 n，计算小于 n 且与 n 不互质的正整数的和

注意是小于 n，这告诉了你在 n = 1 时应该输出 0

想法

欧拉函数入门题

小于 n 且与 n 互质的数的和等于 n * φ(n) / 2

考虑以下事实：
如果 a, b 互质，则 b - a, b 互质（反证法）
把所有小于 n 且与 n 互质的数列出来，得到一张长度为 φ(n) 的表 [a1, a2, ..., am]
接着根据上述推论，列出一张新的表 [n - a1, n - a2, ..., n - am]
神奇的事情发生了
根据我们的推理，两张表都是小于 n 且与 n 互质的数，那么？
这两张表是相同的！
（数学之美

两表对应项相加得 n，两表长度均为 φ(n)，命题得证

题解

剩下的内容就很 naive 了
主要就是调调精度之类的技术细节

某教练：不要使用 #define int long long ！
某教练：把常量都 const 出来！

直接上代码吧

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

template <typename Tp>
inline void read(Tp &x)
{
    x = 0;
    bool neg = 0;

    char c = getchar();
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = 1;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }

    if (neg)
    {
        x = -x;
    }
}

template <typename Tp>
inline const Tp gcd(Tp m, Tp n)
{
    while (n != 0)
    {
        Tp t = m % n;
        m = n;
        n = t;
    }
    return m;
}

const int P = 1e9 + 7;
int n;

inline int phi(int x)
{
    int res = x;
    int _x = sqrt(x);

    for (int i = 2; i <= _x; i++)
    {
        if (x % i == 0)
        {
            res /= i;
            res *= i - 1;

            do
            {
                x /= i;
            } while (x % i == 0);
        }
    }

    if (x != 1)
    {
        res /= x;
        res *= x - 1;
    }

    return res;
}

template <typename Tp>
inline int mod(const Tp &x)
{
    return (x + P) % P;
}

int main()
{
    while (~scanf("%d", &n) && n != 0)
    {
        int p = phi(n);
        int ans = mod((1ll * n * (n - 1) / 2) % P - (1ll * n * p / 2) % P);
        printf("%d\n", ans);
    }
}