SDOI2012 & luogu2303 Longge的问题

发表于

为了填充自己空荡荡的博客，打算写题….

题目背景

SDOi2012

题目描述

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数 $N$ ，你需要求出$\sum\limits_{i = 1}^ngcd(i, n)$。

输入输出格式

输入格式：
一个整数，为 $N$。

输出格式：
一个整数，为所求的答案。

输入输出样例

输入样例#1：

1
6

输出样例#1：

1
15

说明

对于 $60%$ 的数据，$0 < N \leq 2^{16}$
对于 $100%$ 的数据，$0 < N \leq 2^{32}$

题面非常简洁，求 $\sum\limits_{i = 1}^n \gcd(i, n)$

我们设 $t(x)$ 为 $1 - n$ 中与 $n$ 的最大公因数为 $x$ 的数的个数，即

$$ t(x) = \sum_{i = 1}^n[\gcd(i, n) = x]$$

$$ = \sum_{i = 1}^{\lfloor\frac nx\rfloor}[\gcd(i, \lfloor\frac nx\rfloor) = 1] $$

考虑 $\phi(x) = \sum\limits_{i = 1}^n[gcd(i, n) = 1]$
即 $t(x) = \phi(\lfloor\frac nx\rfloor)$

由于$\gcd(i, n) | n$，考虑化简原式为：

$$ \sum\limits_{i = 1}^n\gcd(i, n) $$

$$ = \sum\limits_{d|n}d \times t(d)$$

$$ = \sum\limits_{d|n}d\phi(\frac nd) $$

对于所有 $d | n$ 可以在 $O(\sqrt n)$ 的时间复杂度内枚举，$\phi$ 函数可以在 $O(\sqrt n)$ 的时间复杂度内求出，故时间复杂度为 $O(因数个数 * \sqrt n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>

long long phi(long long n) {
    long long res = n;
    for(long long i = 2; i * i <= n; i++) {
        if(n % i == 0) res = res / i * (i - 1);
        while(n % i == 0) n /= i; 
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}

long long f(long long x) {
    long long res = 0LL, i = 1LL;
    for(; i * i < x; i++)
        if(x % i == 0) res += i * phi(x / i) + (x / i) * phi(i);
    if(i * i == x) res += i * phi(i);
    return res;
}

int main(int argc, char *argv[]) {
    long long n;
    scanf("%lld", &n);
    printf("%lld", f(n));
    return 0;
}