互质是公约数只有1的两个整数,叫做互质整数

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

1.根据定义求解

 求欧拉函数(模板) 算法

 比如1~6中与6互质的数只有1,5,所以6的欧拉函数是2

 

 时间复杂度:O(sqrt(n))

               long res=n;
                        for(int i=2;i<=n/i;i++){
                                if(n%i==0){
                                        res=res*(i-1)/i;
                                        while(n%i==0) n/=i;
                                }
                        }
                        if(n>1) res=res*(n-1)/n;
                        System.out.println(res);

 

2,。

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄