UVA10179 Irreducable Basic Fractions题解

respect_lowsmile · 2022-07-12 21:38:03 · 题解

欧拉函数的应用

今天刚刚学习了同余问题中的欧拉定理，接触了欧拉函数 \varphi(n) ，找到了这道题来练习一下如何求 \varphi(n) 的值。

如果您想学习更多同余知识，您可以戳这里。

一开始链接放错了，给管理大大添麻烦了

首先看题目，大致意思就是给定一个数 N ，求分数 \frac{0}{N} , \frac{1}{N} ··· \frac{N-1}{N} 中有多少分数是可以约分的，这里题目规定 \frac{0}{N} 不可约分 , \frac{1}{N} 可约分，跟我们的正常思路有区别，但是并不影响结果。

description

欧拉函数( \varphi ) ， \varphi(n) 是指小于或等于 n 的数中与 n 互质的数的数目，如 \varphi(8)=4 。

solution

很明显，不能约分的个数就是 \varphi(n) 的值，我们可以运用定理 \varphi(n) = N \times \prod_{i=1}^n(1-\frac{1}{p_i}) 来计算 \varphi(n) 的值，如果想看证明过程可以点上面的链接，只需枚举分解质因数即可。

code

/*
    欧拉函数 
    date:2022.7.12
    worked by respect_lowsmile
*/
#include<iostream>
using namespace std;
int x;
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
}
int phi(int n) 
{
    int ans=n;
    for(int i=2;i*i<=n;++i)
      if(n%i==0)
      {
        ans=ans/i*(i-1);
        while(n%i==0)  n/=i;
      }
    if(n>1)  ans=ans/n*(n-1);
    return ans;
}
int main()
{
    while(x=read())
    {
        if(x==0)  return 0;
        printf("%d\n",phi(x));
    }
    return 0;
}