首先这个翻译完全没说 x 和 S 跟给出的这个可重集有啥关系()而且说成对可重集计数有一种奇怪的感觉,明明是相等的集合却有几次贡献。。。所以建议改为对下标计数。
可以改成这样:
- 有一个长度为 n 的,由 [2,107] 内的整数组成的序列 a,下标为 1 到 n。
- 要求满足条件的一个 [1,n] 内的整数 x 和一个由 [1,n] 内的整数组成的集合 S。
- 条件:x∈/S,i∈Sgcdai>1,gcd(ax,i∈Sgcdai)=1。
- n≤5×105,答案对 109+7 取模。
- 有一个长度为 $n$ 的,由 $[2,10^7]$ 内的整数组成的序列 $a$,下标为 $1$ 到 $n$。
- 要求满足条件的一个 $[1,n]$ 内的整数 $x$ 和一个由 $[1,n]$ 内的整数组成的集合 $S$。
- 条件:$x\notin S$,$\gcd\limits_{i\in S}a_i>1$,$\gcd(a_x,\gcd\limits_{i\in S}a_i)=1$。
- $n\le5\times10^5$,答案对 $10^9+7$ 取模。