线性筛欧拉函数

大致内容

线性筛欧拉函数和线性筛素数其实差不多 只是需要用到一些性质： （以下所有p都为素数）

性质1. $\varphi (p) = p-1$

这个比较显然，因为素数p除了1之外的因数只有p，因此1到p的整数只有p和p自己不互质

性质2. 若 ，那么

证明：

设$b = gcd(n, i)$ 因为n、i不互质，所以$n=k_1b, i=k_2b$ 所以$n +i=(k_1+k_2)b$，即$n+i$与$i$不互质

因为$[1,i]$中与$i$不互质的整数n共有$i-\varphi (i)$个，且$n+i$与$i$不互质

所以$(i,2i]$中与$i$不互质的整数也是$i-\varphi (i)$个

所以$[1, i*p]$中与$i$不互质的整数有$p(i - \varphi(i)) = p*i - p*\varphi(i)$ 个

即$\varphi(i*p)=p*i-(p*i-p*\varphi(i))$

因此$\varphi (i * p) = p * \varphi(i)$

2018.12.16 Update

今天再看这个性质2居然看不太懂了。。。

另外一个比较好理解的证明方法：

由于$\varphi$的另外一种计算方法$\varphi(x)=x*\prod_{i}(1-\frac{1}{p_i})$ 其中$p_i$为$x$的质因子

且此时$i|p$，即$i$已经包含了$i * p$的所有质因子

那么$\varphi(i * p)=i * p * \prod_i(1-\frac{1}{p_i}) = p * \varphi(i)$

性质3. 若 $p\nmid i$，那么$\varphi(i * p)=\varphi(i) * (p - 1)$

由性质1及phi函数为积性函数可知

Code(hdu2824)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
const int Maxn = 3000000 + 100;
int Prime[Maxn], phi[Maxn], NotPrime[Maxn], Cnt;
int N, a, b;
inline void Get_phi()
{
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!NotPrime[i])
        {
            Prime[++Cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= Cnt && i * Prime[j] <= Maxn; ++j)
        {
            NotPrime[i * Prime[j]] = 1;
            if (!(i % Prime[j]))
            {
                phi[i * Prime[j]] = phi[i] * Prime[j];
                break;
            }
            else phi[i * Prime[j]] = phi[i] * (Prime[j] - 1);
        }
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    Get_phi();
    while (scanf("%d%d", &a, &b) != EOF)
    {
        LL Ans = 0;
        for (int i = a; i <= b; ++i) Ans += phi[i];
        cout<<Ans<<endl;
    }
    return 0;
}