博客

欧拉函数，注意细节，读懂题意（要求与n互质的，而不是求与n不互质的）

（“来得很准时。”恺撒看了一眼自己手腕上的百达翡丽，露出淡淡的笑来。

“恺撒对你笑了！”芬格尔大惊小怪的。

路明非惊悚了一下，因为他在那个笑容里忽然看到了情意绵绵……

——江南 《龙族》）

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int main(){
    int n;

    while(scanf("%d",&n)!=EOF&&n!=0){
        int ans=1;

        for(int i=2;i*i<=n;i++){
            int tempnum=1;
            while(n%i==0){
                n=n/i;
                tempnum=tempnum*i;
            }

            if(tempnum==1){
                continue;
            }
            else{
                ans=ans*(tempnum-tempnum/i);//注意此处细节，本来写成了tempnum-tempnum/i+1,因为想着1到tempnum-1之间只有tempnum/i-1个与tempnum不互质的，但是前面tempnum指的是1到tempnum这些数，包括tempnum，所以后面要求的是1到tempnum之间与tempnum不互质的数，所以tempnum/i-1中那个1不应该减去。
            }
        }

        if(n!=1){
            ans=ans*(n-1);
        }

        printf("%d\n",ans);
    }

    return 0;
}