【HUSTOJ】1036:Euler関数
1036:Euler関数
Time Limit: 1 Sec
Memory Limit: 128 MB
Submit: 207
Solved: 48
原題リンク
Description
Euler関数は、nより小さく、nと相互素の正の整数の個数を表す.例えば、(12未満であり、12相互素との正の整数は、1、5、7、11の4つである).
整数n(2<=n<2^31)を与え、計算を要求する値を与える.
Input
整数n.
Output
1行のみ、整数です.
Sample Input
Sample Output
HINT
本題については数学の公式があり、自分で探すことができます.
Source
/*(1)nが素数pのk乗であれば、φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)pは、pの倍数を除いて、他の数がnと相互作用するため
(2)オーラ関数は積性関数である-m,n相互質であれば,φ(mn)=φ(m)φ(n)
特殊な性質:
1)nが奇数の場合、φ(2n)=φ(n)
2)pは素数であり,φ(p) = p - 1,φ(p)pと呼ばれるオーラ値
*/
Time Limit: 1 Sec
Memory Limit: 128 MB
Submit: 207
Solved: 48
原題リンク
Description
Euler関数は、nより小さく、nと相互素の正の整数の個数を表す.例えば、(12未満であり、12相互素との正の整数は、1、5、7、11の4つである).
整数n(2<=n<2^31)を与え、計算を要求する値を与える.
Input
整数n.
Output
1行のみ、整数です.
Sample Input
12Sample Output
4HINT
本題については数学の公式があり、自分で探すことができます.
Source
#include
#include
using namespace std; //
int ol(int n)
{
int s=n,i,m;
m=sqrt(n);
for(i=2;i<=m;i++){
if(n%i==0)
s=s/i*(i-1); //φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)
while(n%i==0)
n/=i; // p
}
if(n>1)
s=s/n*(n-1);
return s;
}
main()
{
int n;
cin>>n;
cout< /*(1)nが素数pのk乗であれば、φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)pは、pの倍数を除いて、他の数がnと相互作用するため
(2)オーラ関数は積性関数である-m,n相互質であれば,φ(mn)=φ(m)φ(n)
特殊な性質:
1)nが奇数の場合、φ(2n)=φ(n)
2)pは素数であり,φ(p) = p - 1,φ(p)pと呼ばれるオーラ値
*/