Description：

随机给 $n$ 个取值范围在 $[1,m]$ 的变量，求他们能线性组合出 $1$ 的概率。

$1\leqslant n,m\leqslant10^{11}$

Solution：

根据裴蜀定理，方程 $ax+by=k$ 有解当且仅当 $\gcd(a,b)|k$ ，其实裴蜀定理还可以扩展到很多变量的形式，即： $$ \sum_{i=1}^nx_ia_i=k $$ 有解当且仅当 $\gcd(a_1,a_2,\dots,a_n)|k$ 。

所以这题实际就是让求： $$ \sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m[\gcd(i_1,i_2,\dots,i_n)=1] $$ 反演一下，枚举一个 $\mu$ ，就变成了： $$ \sum_{k=1}^m\mu(k)\lfloor\frac m k\rfloor^n $$ 然后就是杜教筛 $+$ 除法分块了。

Code：