Description

Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数,为N。

Output

一个整数,为所求的答案。

Sample Input

6

Sample Output

15

HINT

【数据范围】

对于60%的数据,0<N<=2^16。

对于100%的数据,0<N<=2^32。

 

题解

$$begin{aligned}
&sum_{i=1}^N gcd(i, N)\
&= sum_{d|N} dsum_{i=1}^N [gcd(i, N) = d]\
&= sum_{d|N} dsum_{d|t} muleft(frac tdright)sum_{i=1}^N [t|gcd(i,N)]\
&= sum_{t|N} frac Ntsum_{d|t} dmuleft(frac tdright)\
&= sum_{t|N} frac Ntphi(t)
end{aligned}$$
预处理N的质因子,枚举其因数即可。

代码:

#include <cstdio>
typedef long long LL;
const int M = 100;
int n;
LL ans;
int pr[M], prcnt;
inline void calc(int x) {
  int anst = x;
  for (int i = 0; i < prcnt; ++i) if (!(x % pr[i]))
    anst = anst / pr[i] * (pr[i] - 1);
  ans += (LL)n / x * anst;
}
int main() {
  scanf("%d", &n);
  int tn = n;
  for (int i = 2; (LL)i * i <= tn; ++i)
    if (!(tn % i)) {
      pr[prcnt++] = i;
      while (!(tn % i)) tn /= i;
    }
  if (tn > 1)
    pr[prcnt++] = tn;
  for (int i = 1; (LL)i * i <= n; ++i) if (!(n % i)) {
    calc(i);
    if (i != n / i) calc(n / i);
  }
  printf("%lldn", ans);
  return 0;
}

  

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!