题意
对于一个长度为(n)的序列(A={a_i})以及正整数(m),定义(f(A,m))为(sumlimits_{i=1}^n a_ix_iequiv 0( ext{mod}~m)(forall i, ext{s.t.}x_iin[0,m)]))的解的个数。
给定一个长度为(n)的序列(B),给定(M)。
令(w_m=sumlimits_{S eq emptyset,Ssubseteq B}f(S,m)),求(iin[1,M])所有的(w_i)((w_m)对质数取模)。
(1le n,b_i,Mle 10^5)
做法
引理:(f(A,m)=gcd(A,m)cdot m^{|A|-1})。
证明:
显然,如果我们能证明(f(A,p^k)=gcd(A,p^k)cdot (p^k)^{|A|-1}),则引理得证。
令(b_i=a_i\% p^k),假设(b_i=c_ip^{q_i}((c_i,p)=1))
由于(c_i)有逆元,(f(A,p^k))为(sumlimits_{i=1}^n p_i^{q_i}x_iequiv 0( ext{mod}~p^k)(forall i, ext{s.t.}x_iin[0,p^k)]))的解的个数。
一般的,令(q_1=min{q_i})。
假设(x_i(i eq 0))为常数,(p^{q_1}x_1+sumlimits_{i=2}^n p^{q_i}x_iequiv 0(mod~p^k))有解的充要条件为:(sumlimits_{i=2}^n p^{q_i}x_i)是((p^k,p^{q_1})=p^{q_1})的倍数。
由于(q_1=min{q_i}),显然是有解的。且(x_1)的解的个数为((p^k,p^{q_1})=p^{q_1})。
那么(f(A,p^k)=p^{q_1}cdot (p^k)^{|A|-1}=gcd(A,m)cdot m^{|A|-1})。
令(C_i)为整除(i)的个数。
于是,此题可以在(O(sumlimits_{i=1}^n sigma(b_i)+m ext{ln}m))复杂度内解决。