【HDU 1286】找新朋友

找新朋友（题目链接）

思路

• 直接暴力，TLE
• 使用map存储中间计算值优化，TLE
• 使用欧拉函数计算，AC

代码

#include <iostream>
#include <map>
using namespace std;
#define LOCAL 0

//返回小于n且与n互质的数的个数 
int euler(int n){ 
    int ans = n;
    int tmp = n;
    for(int i = 2; i*i <= tmp; i++){
        if(tmp%i == 0){
            ans = ans / i * (i - 1); 
            while(tmp % i == 0){
                tmp /= i;            
            } 
        }
    }
    if(tmp>1) {
        ans = ans / tmp * (tmp-1);
    }
    return ans;
}

int main(){   
#if LOCAL
    freopen ("datain.txt","r",stdin);
    freopen ("dataout.txt","w",stdout);
#endif
    
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        int t;
        cin >> t;
        cout << euler(t) << endl;
    }
        
    return 0;
}