对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。
此题题意正是求这个函数
φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，
x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3
那么φ（12）=12*（1-1/2）*(1-1/3)=4)
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。
http://baike.baidu.com/view/107769.htm#sub107769
自己写的186MS，欧拉函数写的15MS，但是还有cow 0MS过的，YM……
AC代码
#include
<
iostream
>
#include
<
cmath
>
#include
<
cstring
>
using
namespace
std;
int
main()
{
int
i,n,m,cas,num;
int
yue[
1000
];
scanf(
“
%d
“
,
&
cas);
while
(cas
—
)
{
scanf(
“
%d
“
,
&
n);
num
=
0
;
m
=
n;
for
(i
=
2
;i
<=
sqrt((
double
)m);i
++
)
{
if
(m
%
i
==
0
)
{
yue[num
++
]
=
i;
m
/=
i;
}
while
(m
%
i
==
0
)
{
m
/=
i;
}
}
if
(m
!=
1
){
yue[num
++
]
=
m;
}
double
b
=
double
(n);
for
(i
=
0
;i
<
num;i
++
)
{
b
*=
(
1
–
1.0
/
(
double
)yue[i]);
}
cout
<<
int
(b)
<<
endl;
return
0
;
}
<
iostream
>
#include
<
cmath
>
#include
<
cstring
>
using
namespace
std;
int
main()
{
int
i,n,m,cas,num;
int
yue[
1000
];
scanf(
“
%d
“
,
&
cas);
while
(cas
—
)
{
scanf(
“
%d
“
,
&
n);
num
=
0
;
m
=
n;
for
(i
=
2
;i
<=
sqrt((
double
)m);i
++
)
{
if
(m
%
i
==
0
)
{
yue[num
++
]
=
i;
m
/=
i;
}
while
(m
%
i
==
0
)
{
m
/=
i;
}
}
if
(m
!=
1
){
yue[num
++
]
=
m;
}
double
b
=
double
(n);
for
(i
=
0
;i
<
num;i
++
)
{
b
*=
(
1
–
1.0
/
(
double
)yue[i]);
}
cout
<<
int
(b)
<<
endl;
}
return
0
;
}
转载于:https://www.cnblogs.com/cykun/archive/2011/04/18/2020288.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110632.html原文链接：https://javaforall.net
