hdu 2824 The Euler function

제목 링크:hdu 2824 The Euler function
오라 함수를 계산합니다. 오라 함수 $\phi(x)$는 $x$를 초과하지 않고 $x$와 호환되는 정수의 개수입니다.여기에는 두 가지 해답 방법이 있다.

방법 1:

분명히 오라 함수는 다음과 같은 세 가지 성질이 있다.
1, $\phi(x=p) = p-1$, $x$가 질수일 때, $k\in[1, p-1]$의 $p-1$개수는 모두 $p$와 호환됩니다.
2, $\phi(x=p^n) = p^n - p^ {n-1}$, $x$가 질수의 $n$차방일 때, $p, 2p, 3p,\cdots, p^ {n-1}p$이 $p^ {n-1}$개 이외의 수는 $x$와 상호작용합니다.
3, $\phi (x = ab) =\phi (a)\phi (b) $, $x$가 두 수의 곱셈과 같을 때, 그 오라 함수는 곱셈을 가진다.등식 왼쪽에 $\phi (ab) $개 수의 집합을 만들고, 등식 오른쪽에 $\phi (a)\phi (b) $개 질서 쌍을 만듭니다. 즉, $a$상호작용과 $b$상호작용의 수의 집합에서 각각 질서 쌍을 만듭니다.중국의 잉여 정리에 따르면 이 두 집합이 일일이 대응하는 것을 발견할 수 있다.
따라서 모든 정수 $x$에 대한 오라함의 값은 다음과 같습니다.
\begin{equation}\phi(x =\prod_i^j p_i^{k_i} )=\prod_i^j p_i^{k_i} - p_i^{k_i-1}\end{equation}
그러나 이 방법은 $x$에 대해 질인수분해를 해야 하기 때문에 프로그래밍의 복잡도가 비교적 높다.

방법 2:

$\phi(x=\prod_i^jp_i^{k_i})$를 구하려면 배율 원리를 사용할 수 있습니다.즉,
\begin{equation}\phi(x) =\sum_{S\subset\{p_i,i\in[1,j]\}} (-1)^{|S|}\frac{x}{\prod_{p_i\in S}p_i}\end{equation}
다음과 같이 단순화할 수 있습니다.
\begin{equation}\phi(x) = x\prod_{i = 1}^j(1-\frac{1}{p_i})\end{equation}
모든 항목에서 $1$또는 $-\frac {1} {p_i}$를 선택할 수 있기 때문에, 모두 곱하면 $x$를 얻을 수 있습니다.2식 정의와 같습니다.
이 문제에 대해 먼저 체법을 사용하여 주어진 범위 내의 모든 수의 오라 함수 값을 구하고 화합을 구한다.
코드는 다음과 같습니다.

 1 #include <cstdio>

 2 #include <cstdlib>

 3 #include <iostream>

 4 #include <cstring>

 5 #define     MAXN 3000003

 6 using namespace std;

 7 int phi[MAXN];

 8 void init()

 9 {

10     for( int i = 1 ; i < MAXN ; i++ )

11     {

12         phi[i] = i;

13     }

14     for( int i = 2 ; i < MAXN ; i++ )

15     {

16         if( phi[i] == i )

17         {

18             phi[i] = i -1;

19             for( int j = i*2 ; j < MAXN ; j += i )

20             {

21                 phi[j] = phi[j]/i*(i-1);

22             }

23         }

24     }

25 }

26 int main(int argc, char *argv[])

27 {

28     int a, b;

29     init();

30     while( scanf("%d%d", &a, &b) != EOF )

31     {

32         long long ans = 0;

33         for( int i = a ; i <= b ; i++ )

34         {

35             ans += phi[i];

36         }

37         cout<<ans<<endl;

38     }

39 }