51Nod1594 Gcd and Phi

题目看这里
一个简单的反演题目:

\sum_{i = 1}^{n} \sum_{j = 1}^{n} ϕ (g c d (ϕ (i), ϕ (j)))

首先做一下变换

\sum_{i = 1}^{n} \sum_{j = 1}^{n} ϕ (g c d (ϕ (i), ϕ (j)))

= \sum_{d = 1}^{n} ϕ (d) * f (d)

这里

f (d) = \sum_{i, j} [g c d (ϕ (i), ϕ (j)) = d]

表示有多少对i,j满足它们的

ϕ

值的最大公约数为d
我们令

F (d) = \sum_{i, j} [d | g c d (ϕ (i), ϕ (j))]

,就有

F (n) = \sum_{n | d} f (d)

反演得到

f (n) = \sum_{d} F (n * d) * μ (d)

所以原式可以写成

\sum_{i * j <= n} ϕ (i) * F (i * j) * μ (j)

预处理

μ, ϕ

和

F

的值就可以了

# p r a g m a G C C o p t i m i z e (" O 3 ")

# p r a g m a G + + o p t i m i z e (" O 3 ")

# i n c l u d e < s t d i o . h >

# i n c l u d e < s t r i n g . h >

# i n c l u d e < a l g o r i t h m >

# d e f i n e N 2000010

# d e f i n e L L l o n g l o n g

u s i n g n a m e s p a c e s t d;

i n t n, T; l o n g l o n g S;

i n t w [N >> 2], t, p h i [N], m u [N], v i s [N], c [N];

i n l i n e L L F (i n t x) {r e t u r n (L L) c [x] * c [x];}

i n l i n e v o i d c a l () {

s c a n f (" % d ", & n); m e m s e t (c, S = 0, s i z e o f c);

f o r (i n t i = 1; i <= n; + + i) + + c [p h i [i]];

f o r (i n t i = 1; i <= n; + + i)

f o r (i n t j = i + i; j <= n; j + = i) c [i] + = c [j];

f o r (i n t i = 1; i <= n; + + i) i f (m u [i])

f o r (i n t j = 1; i * j <= n; + + j)

S + = (L L) F (i * j) * m u [i] * p h i [j];

p r i n t f (" % l l d ", S);

}

i n t m a i n () {

p h i [1] = m u [1] = 1;

f o r (i n t i = 2; i <= 2000000; + + i) {

i f (! v i s [i]) {m u [w [+ + t] = i] = - 1; p h i [i] = i - 1;}

f o r (i n t j = 1, k; (k = i * w [j]) <= 2000000; + + j) {

v i s [k] = 1;

i f (i % w [j] == 0) {p h i [k] = p h i [i] * w [j]; m u [k] = 0; b r e a k;}

p h i [k] = p h i [i] * (w [j] - 1); m u [k] = - m u [i];

}

}

f o r (s c a n f (" % d ", & T); T - -; c a l ());

}