文章目录
题目分析代码
题目
[CodeForces 439E] Devu and Birthday Celebration
分析
莫比乌斯函数比较重要的性质：
μ
∗
1
=
ε
\mu * 1 = \varepsilon
μ∗1=ε 即
∑
d
∣
n
μ
(
d
)
=
[
n
=
1
]
\sum_{d | n}\mu(d) = [n = 1]
d∣n∑μ(d)=[n=1]
证明： 设
n
=
∏
i
=
1
m
p
i
α
i
n = \prod_{i = 1}^{m} p_i^{\alpha_i}
n=∏i=1mpiαi，
n
′
=
∏
i
=
1
m
p
i
n' = \prod_{i = 1}^mp_i
n′=∏i=1mpi，有
∑
d
∣
n
μ
(
d
)
=
∑
d
∣
n
′
μ
(
d
)
=
∑
i
=
0
m
(
m
i
)
(
−
1
)
i
\sum_{d | n}\mu(d) = \sum_{d | n'}\mu(d) = \sum_{i = 0}^{m} \binom{m}{i} (-1)^i
d∣n∑μ(d)=d∣n′∑μ(d)=i=0∑m(im)(−1)i 由二项式定理，当
n
=
1
n = 1
n=1 时，上式为
1
1
1；当
n
≠
1
n \neq 1
n=1 时，上式为
[
1
+
(
−
1
)
]
m
=
0
[1 + (-1)]^m = 0
[1+(−1)]m=0。
∑
a
1
=
1
n
∑
a
2
=
1
n
⋯
∑
a
f
=
1
n
[
∑
i
=
1
f
a
i
=
n
]
[
gcd
i
=
1
f
a
i
=
1
]
=
∑
a
1
=
1
n
∑
a
2
=
1
n
⋯
∑
a
f
=
1
n
[
∑
i
=
1
f
a
i
=
n
]
∑
d
∣
gcd
i
=
1
f
a
i
μ
(
d
)
=
∑
d
∣
n
μ
(
d
)
∑
k
1
=
1
n
d
∑
k
2
=
1
n
d
⋯
∑
k
f
=
1
n
d
[
∑
i
=
1
f
k
i
=
n
d
]
\begin{aligned} &\sum_{a_1 = 1}^n \sum_{a_2 = 1}^n \cdots \sum_{a_f = 1}^n \left[\sum_{i = 1}^fa_i = n\right] \left[\gcd_{i = 1}^f a_i = 1\right] \\ =& \sum_{a_1 = 1}^n \sum_{a_2 = 1}^n \cdots \sum_{a_f = 1}^n \left[\sum_{i = 1}^f a_i = n\right] \sum_{d |\text{gcd}_{i = 1}^f a_i} \mu(d) \\ =& \sum_{d | n} \mu(d) \sum_{k_1 =1}^{\frac{n}{d}} \sum_{k_2 =1}^{\frac{n}{d}} \cdots \sum_{k_f =1}^{\frac{n}{d}} \left[\sum_{i = 1}^f k_i = \frac{n}{d} \right]\end{aligned}
==a1=1∑na2=1∑n⋯af=1∑n[i=1∑fai=n][i=1gcdfai=1]a1=1∑na2=1∑n⋯af=1∑n[i=1∑fai=n]d∣gcdi=1fai∑μ(d)d∣n∑μ(d)k1=1∑dnk2=1∑dn⋯kf=1∑dn[i=1∑fki=dn]（转换枚举方式，
a
i
=
d
⋅
k
i
a_i = d\cdot k_i
ai=d⋅ki，由于
d
∣
a
i
d | a_i
d∣ai，所以
d
∣
∑
i
=
1
f
a
i
d | \sum_{i = 1}^f a_i
d∣∑i=1fai 即
d
∣
n
d | n
d∣n）
预处理莫比乌斯函数，然后
O
(
n
)
O(\sqrt{n})
O(n
) 枚举因数 + 隔板法即可。
代码
#include <bits/stdc++.h>
typedef long long LL
;
template <const int _MOD
> struct ModNumber
{
int x
;
inline ModNumber() { x
= 0; }
inline ModNumber(const int &y
) { x
= y
; }
inline int Int() { return x
; }
inline ModNumber
Pow(int y
) const { register int ret
= 1, tmp
= x
; while (y
) { if (y
& 1) ret
= ((LL
)ret
* tmp
) % _MOD
; y
>>= 1; tmp
= ((LL
)tmp
* tmp
) % _MOD
; } return ModNumber(ret
); }
inline bool operator == (const ModNumber
&y
) const { return x
== y
.x
; }
inline bool operator != (const ModNumber
&y
) const { return x
!= y
.x
; }
inline bool operator < (const ModNumber
&y
) const { return x
< y
.x
; }
inline bool operator > (const ModNumber
&y
) const { return x
> y
.x
; }
inline bool operator <= (const ModNumber
&y
) const { return x
<= y
.x
; }
inline bool operator >= (const ModNumber
&y
) const { return x
>= y
.x
; }
inline ModNumber
operator - () const { return _MOD
- x
; }
inline ModNumber
operator + (const ModNumber
&y
) const { return (x
+ y
.x
>= _MOD
) ? (x
+ y
.x
- _MOD
) : (x
+ y
.x
); }
inline ModNumber
operator - (const ModNumber
&y
) const { return (x
- y
.x
< 0) ? (x
- y
.x
+ _MOD
) : (x
- y
.x
); }
inline ModNumber
operator * (const ModNumber
&y
) const { return ModNumber((LL
)x
* y
.x
% _MOD
); }
inline ModNumber
operator / (const ModNumber
&y
) const { return *this * y
.Pow(_MOD
- 2); }
inline ModNumber
operator ^ (const int &y
) const { return Pow(y
); }
inline void operator += (const ModNumber
&y
) { *this = *this + y
; }
inline void operator *= (const ModNumber
&y
) { *this = *this * y
; }
inline void operator -= (const ModNumber
&y
) { *this = *this - y
; }
inline void operator /= (const ModNumber
&y
) { *this = *this / y
; }
inline void operator ^= (const int &y
) const { *this = *this ^ y
; }
inline bool operator == (const int &y
) const { return x
== y
; }
inline bool operator != (const int &y
) const { return x
!= y
; }
inline bool operator < (const int &y
) const { return x
< y
; }
inline bool operator > (const int &y
) const { return x
> y
; }
inline bool operator <= (const int &y
) const { return x
<= y
; }
inline bool operator >= (const int &y
) const { return x
>= y
; }
inline ModNumber
operator + (const int &y
) const { return (x
+ y
>= _MOD
) ? (x
+ y
- _MOD
) : (x
+ y
); }
inline ModNumber
operator - (const int &y
) const { return (x
- y
< 0) ? (x
- y
+ _MOD
) : (x
- y
); }
inline ModNumber
operator * (const int &y
) const { return ModNumber((LL
)x
* y
% _MOD
); }
inline ModNumber
operator / (const int &y
) const { return *this * ModNumber(y
).Pow(_MOD
- 2); }
inline void operator += (const int &y
) { *this = *this + y
; }
inline void operator *= (const int &y
) { *this = *this * y
; }
inline void operator -= (const int &y
) { *this = *this - y
; }
inline void operator /= (const int &y
) { *this = *this / y
; }
};
const int MAXN
= 2 * 100000;
const int MOD
= 1000000007;
typedef ModNumber
<MOD
> Int
;
Int Fac
[MAXN
+ 5], Inv
[MAXN
+ 5];
Int Mu
[MAXN
+ 5];
bool Vis
[MAXN
+ 5];
std
::vector
<int> Primes
;
void Init(int n
) {
Mu
[1] = 1;
for (int i
= 2; i
<= n
; i
++) {
if (!Vis
[i
])
Mu
[i
] = MOD
- 1, Primes
.push_back(i
);
for (int j
= 0; j
< (int)Primes
.size() && i
* Primes
[j
] <= n
; j
++) {
Vis
[i
* Primes
[j
]] = true;
if (i
% Primes
[j
] == 0) {
Mu
[i
* Primes
[j
]] = 0;
break;
}
Mu
[i
* Primes
[j
]] = -Mu
[i
];
}
}
Fac
[0] = 1;
for (int i
= 1; i
<= n
; i
++)
Fac
[i
] = Fac
[i
- 1] * i
;
Inv
[n
] = Fac
[n
] ^ (MOD
- 2);
for (int i
= n
- 1; i
>= 0; i
--)
Inv
[i
] = Inv
[i
+ 1] * (i
+ 1);
}
Int
C(int n
, int m
) {
if (n
< m
) return 0;
return Fac
[n
] * Inv
[m
] * Inv
[n
- m
];
}
int main() {
Init(MAXN
);
int Q
; scanf("%d", &Q
);
while (Q
--) {
Int Ans
= 0;
int N
, F
; scanf("%d%d", &N
, &F
);
for (int i
= 1; i
* i
<= N
; i
++) {
if (N
% i
) continue;
int j
= N
/ i
; Ans
+= Mu
[i
] * C(j
- 1, F
- 1);
if (j
!= i
) Ans
+= Mu
[j
] * C(i
- 1, F
- 1);
}
printf("%d\n", Ans
.x
);
}
return 0;
}
