记录编号	406157	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]艾米利亚的求助	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.932 s
提交时间	2017-05-17 23:16:43	内存使用	0.29 MiB

#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
LL sum(LL n){
  int m = (int)(sqrt(n)+0.5);
  long long cnt = 0;
  for(int i = 1; i <= m; i++){
    if(n%i == 0){
      cnt += i;
      if(i*i != n)cnt += n/i;
      else break;
    }
  }
  return cnt;
}
LL phi(LL n){
  int m = (int)(sqrt(n)+0.5);
  long long ans = n;
  for(int i = 2; i <= m; i++){
    if(n%i == 0){
      ans = ans/i*(i-1);
      while(n%i == 0)n /= i;
      if(n == 1)break;
    }
  }
  if(n > 1)ans = ans/n*(n-1);
  return ans;
}
int main(){
  freopen("aimiliyadehelp.in", "r", stdin);
  freopen("aimiliyadehelp.out", "w", stdout);
  LL n; scanf("%lld", &n);
  printf("%lld\n", sum(n)-phi(n));
  return 0;
}