摘要：
1136欧拉函数基准时间限制：1秒空间限制：131072KB分数：0难度：基本问题集中在正整数n上。欧拉函数是小于或等于n的数字的数量。该函数以第一位研究者欧拉的名字命名。它也被称为欧拉停止函数φ函数、欧拉商等。例如：φ=4，因为1,3,5,7与8互素。输入输入数字N。输入示例8输出示例4想法：模板问题#include 整数，ans；intGet_ Phi｛inti，m=n；ans=n；forif//查找第一个素因子｛ans=ans/i*（i-1）；//应用欧拉函数的性质，同时//减少所有素因子n/=i；｝如果（n˃1）ans=ans/n*（n-1）；返回者；}intmain（）{while（scanf（“%d”，&n）！
收藏
关注对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。
Input
输入一个数N。(2 <= N <= 10^9)
Output
输出Phi(n)。
Input示例
8
Output示例
4
思路：模板题。
#include<stdio.h> int n,ans; int Get_phi(int n) { int i,m=n; ans = n; for(i = 2; i*i <= m; 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(scanf("%d",&n)!=EOF) { ans = Get_phi(n); printf("%d ",ans); } return 0; }