【LOJ2523】【BZOJ5302】【HAOI2018】奇怪的背包

裴蜀定理+容斥即可。

首先考虑经典的裴蜀定理:i=1nxiai=d\sum_{i=1}^nx_ia_i=d有整数解当且仅当gcd(a1,a2,,an)d\gcd(a_1,a_2,\cdots,a_n) \mid d

注意本题并不需要非负的条件,因为可以用PP来调整。

于是问题就变成了求

SVi[gcd(S,P)wi] \sum_{S\in V_i}[\gcd(S,P)\mid w_i]

首先ViV_iwiw_i显然都可以先和PPgcd\gcd

然后设kkPP的约数个数,根据vfk的blog,当P109P\le 10^9时有k1344k \le 1344

那么我们考虑先对于每个xPx\mid P求出

SVi[xgcd(S,P)] \sum_{S\in V_i}[x \mid\gcd(S,P)]

显然这就是2m12^m-1,其中

m=i=1n[xai] m=\sum_{i=1}^n[x \mid a_i]

O(k2)O(k^2)暴力即可。

之后我们O(k2)O(k^2)暴力容斥求得

SVi[x=gcd(S,P)] \sum_{S\in V_i}[x =\gcd(S,P)]

然后再O(k2)O(k^2)统计答案即可。

时间复杂度O(k2+(n+q)logk)O(k^2+(n+q) \log k)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=20000020;
const int mod=1000000007;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("2532.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int d[2002];
ll cnt[2002];
int pw[1000002];
int main(){
    init();
    int n=readint(),q=readint(),p=readint(),cur=0;
    for(int i=1;i*i<=p;i++)
        if (p%i==0){
            d[++cur]=i;
            if (i*i!=p)
                d[++cur]=p/i;
        }
    sort(d+1,d+cur+1);
    pw[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*2;
        if (pw[i]>=mod)
            pw[i]-=mod;
    }
    while(n--)
        cnt[lower_bound(d+1,d+cur+1,__gcd(readint(),p))-d]++;
    for(int i=1;i<=cur;i++)
        for(int j=i+1;j<=cur;j++)
            if (d[j]%d[i]==0)
                cnt[i]+=cnt[j];
    for(int i=1;i<=cur;i++)
        cnt[i]=pw[cnt[i]]-1;
    for(int i=cur;i;i--){
        for(int j=i+1;j<=cur;j++)
            if (d[j]%d[i]==0)
                cnt[i]-=cnt[j];
        cnt[i]%=mod;
    }
    for(int i=cur;i;i--){
        for(int j=1;j<i;j++)
            if (d[i]%d[j]==0)
                cnt[i]+=cnt[j];
        cnt[i]=(cnt[i]%mod+mod)%mod;
    }
    while(q--)
        printf("%lld\n",cnt[lower_bound(d+1,d+cur+1,__gcd(readint(),p))-d]);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2018/06/11/loj2523/

隐藏