题目概述

给你 $n$ 种物品，每种物品有无数个，体积为 $V_i$ ，选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ，问方案数。

解题报告

怎么我一道HAOI题都不会啊，我实在太菜了（HAOI题太假了）。

写成柿子就是验证是否存在 $\{a_{k+1}\}$ 使得 $\sum_{i=1}^{k}a_iV_i\equiv w(mod\ p)\Leftrightarrow \sum_{i=1}^{k}a_iV_i-a_{n+1}p=w$ ，如果 $k=2$ 的话那么就是裴蜀定理，实际上裴蜀定理可以推广到 $k$ 元线性同余方程，就是验证 $(V_1,V_2,\cdots,V_k,p)|w$ ，yy一下还是很显然的（不就是不会证吗，直接说不就好了）。然后我就不会做了QAQ，看题解……

再变形一下就是 $((V_1,p),(V_2,p),\cdots,(V_k,p))|(w,p)$ 。为什么这样变形？因为你会发现这么变形之后所有元素就限制在了 $p$ 的因子内！然后你就可以瞎搞了：定义 $f_{i,j}$ 表示用前 $i$ 个因子 $gcd$ 出第 $j$ 个因子的方案数，对于每个因子转移一下，最后 $O(1)$ 回答。

$10^9$ 之内因子个数是 $O(10^3)$ 的，颠覆了我的世界观……看来下次看到这种题要多往因子方面想……

示例程序

#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int maxd=10000,maxn=1000000,MOD=1e9+7;

int n,te,P,D[maxd+5],num[maxd+5],f[2][maxd+5];
int pw[maxn+5];unordered_map<int,int> ID;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline void Make(int x){
    for (int i=1,S=sqrt(x);i<=S;i++)
        if (!(x%i)) {D[++D[0]]=i;if (i<x/i) D[++D[0]]=x/i;}
    sort(D+1,D+1+D[0]);for (int i=1;i<=D[0];i++) ID[D[i]]=i;
}
int gcd(int a,int b) {if (!b) return a;return gcd(b,a%b);}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    readi(n);readi(te);readi(P);Make(P);
    for (int i=1,x;i<=n;i++) readi(x),num[ID[gcd(x,P)]]++;
    pw[0]=1;for (int i=1;i<=n;i++) pw[i]=((LL)pw[i-1]<<1)%MOD;
    for (int i=1,c=1;i<=D[0];i++,c^=1){
        for (int j=1;j<=D[0];j++) f[c][j]=f[c^1][j];AMOD(f[c][i],pw[num[i]]-1);
        for (int j=1;j<=D[0];j++) AMOD(f[c][ID[gcd(D[i],D[j])]],(LL)f[c^1][j]*(pw[num[i]]-1)%MOD);
    }
    for (int i=D[0];i>1;i--)
        for (int j=i-1;j;j--)
            if (!(D[i]%D[j])) AMOD(f[D[0]&1][i],f[D[0]&1][j]);
    for (int i=1,x;i<=te;i++) readi(x),x=gcd(x,P),printf("%d\n",f[D[0]&1][ID[x]]);
    return 0;
}