主题思想
容斥原理应用
注意细节
二进制记录状态是很实用的技巧,要牢记
基础代码
package main
import (
"fmt"
"bufio"
"os"
)
const N = 20
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewReader(os.Stdin)
p [N]int
)
func main() {
n, m := 0, 0
fmt.Fscan(in, &n, &m)
for i := 0; i < m; i++ { fmt.Fscan(in, &p[i]) }
res := 0
for i := 1; i < (1 << m); i++ {
t, s := 1, 0
for j := 0; j < m; j++ {
if (i >> j) & 1 > 0 {
if t * p[j] > n {
t = -1
break
}
t *= p[j]
s++
}
}
if t != -1 {
if s % 2 == 0 {
res -= n / t
} else {
res += n / t
}
}
}
fmt.Fprint(out, res)
out.Flush()
}