题意简洁明了。做这题主要是温习一下phi的求法。令gcd(i,n)=k，实际上我们只需要求出有多少个i使得gcd(i,n)=k就可以了，然后就转化成了求phi(n/k)的和，但是n很大，我们不可能预处理出所有的phi，但是因为k的个数是O(sqrt(n))级别的，所以我们只需要求出sqrt(n)个数的phi就可以了，我们先预处理出所有的质因子及其个数，然后dfs一下就可以了。

#pragma warning(disable:4996)#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;int n;int cnt[35];int prime[35];int tot;ll ans;void dfs(int step, int phi){ if (step == tot){ ans += (ll)phi; return; } dfs(step + 1, phi); phi = phi / prime[step] * (prime[step] - 1); for (int i = 0; i < cnt[step]; i++){ dfs(step + 1, phi); }}int main(){ while (~scanf("%d",&n)) { memset(cnt, 0, sizeof(cnt)); tot = 0; int x = n; for (ll i = 2; i*i <= x; i++){ if (x%i == 0){ for (; x%i == 0; x /= i) cnt[tot]++; prime[tot++] = i; } if (x == 1) break; } if (x != 1) cnt[tot]++, prime[tot++] = x; ans = 0; dfs(0, n); printf("%lld\n", ans); } return 0;}