首先考虑容斥，记 $F_i$ 为至少存在 $i$ 个平方数的方案数，则

$$\text{Answer} = \sum_{i=0}^n (-1)^i \times \binom n i \times F_i$$

求 $\sum_{x=1}^n\sum_{y=1}^m\frac{x}{y}​$ 在 $k$ 进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数

​一眼看上去就是期望 DP，然而蒟蒻不会，在同机房神仙讲解下豁然开朗，于是写篇题解。

蒟蒻模拟赛题啥都不会

比赛时打了个 $O(n^2m^2)$ 的暴力还WA了