void
eular()
{
memset(vis,
0
,
sizeof
(vis));
vis[
0
]=vis[
1
]=
1
;
for
(i=
2
;i*i<=N;i++
)
{
if
(vis[i]==
0
)
{
for
(j=i*i;j<=N;j+=
i)
vis[j]
=
1
;
}
}
//
这段求出了N内的所有素数
for
(i=
1
;i<=N;i++
)
phi[i]
=
i;
for
(i=
2
;i<=N;i++
)
{
if
(vis[i]==
0
)
{
for
(j=i;j<=N;j+=i)
//
这里从i开始，必定能整除i，其倍数也同理
phi[j]=phi[j]/i*(i-
1
);
//
此处注意先/i再*（i-1)，否则范围较大时会溢出
}
}
}
递归求欧拉函数
for
(i =
1
; i <= maxn; i++) phi[i] =
i;
for
(i =
2
; i <= maxn; i +=
2
) phi[i] /=
2
;
for
(i =
3
; i <= maxn; i +=
2
)
if
(phi[i] ==
i) {
for
(j = i; j <= maxn; j +=
i)
phi[j]
= phi[j] / i * (i -
1
);
单独求欧拉函数
unsigned euler(unsigned x)
{
//
就是公式
unsigned i, res=
x;
for
(i =
2
; i < (
int
)sqrt(x *
1.0
) +
1
; i++
)
if
(x%i==
0
)
{
res
= res / i * (i -
1
);
while
(x % i ==
0
) x /= i;
//
保证i一定是素数
}
if
(x >
1
) res = res / x * (x -
1
);
return
res;
}
