数列的 GCD [计数问题]

$数列的GCD$数列的GCD

$Description$Description

$Solution$Solution

由于有 $K$K 个位置两数列不相同, 于是 使用 $\left\{a_n\right\}${an​} 构造 $\left\{b_n\right\}${bn​},

枚举 $d$d, 即假设 $d$d 是已知量,
设 $\left\{a_n\right\}${an​} 有 $x$x 个位置不能整除 $d$d,
由于 $条件2$条件2的限制, 这 $x$x 个位置需要改变,
即至少改变 $x$x个位置, 若 $x\>K$x>K, 说明无解 .

于是若存在答案, 则 $x\&lt;=K$x<=K,
$x$x 个位置的数要改变, 方案数为
$\begin{array}{}\text{(1)}& \lfloor \frac{M}{d}{\rfloor }^x\end{array}$⌊dM​⌋x(1)
剩下还需改变 $K-x$K−x 个位置上的数, 方案数为
$\begin{array}{}\text{(2)}& \left(\frac{N}{N-x}\right)\ast \lfloor \frac{M}{d}-1{\rfloor }^{K-x}\end{array}$(N−xN​)∗⌊dM​−1⌋K−x(2)

$\begin{array}{}\text{( (1) * (2) )}& \therefore tmp\left[d\right]=\lfloor \frac{M}{d}{\rfloor }^x\left(\frac{N}{N-x}\right)\lfloor \frac{M}{d}-1{\rfloor }^{K-x}\end{array}$∴tmp[d]=⌊dM​⌋x(N−xN​)⌊dM​−1⌋K−x( (1) * (2) )

由于 $gcd$gcd 为 $d$d, 所以要减去 $gcd$gcd 是 $Ans\left[d\right]$Ans[d] 倍数的方案
$Ans\left[d\right]=tmp\left[d\right]-tmp\left[2d\right]-tmp\left[3d\right]-...-tmp\left[nd\right]$Ans[d]=tmp[d]−tmp[2d]−tmp[3d]−...−tmp[nd]

$Codewithbug$Code with bug

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ c = getchar(), flag = -1; break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 300005;
const int mod = 1000000007;

int N;
int M;
int K;
int x;
int A[maxn];
int jc[maxn];
int rev[maxn];
int tmp[maxn];
int Ans[maxn];

int C(int n, int m){
        int fz = jc[n];
        int fm = 1ll*jc[n-m]*jc[m] % mod;
        fz = 1ll*fz*rev[fm] % mod;
        return fz;
}

int KSM(int a, int b){
        int s = 1;
        while(b){
                if(b & 1) s = 1ll*s*a % mod;
                a = 1ll*a*a % mod;
                b >>= 1;
        }
        return s;
}

void Init(){
        rev[1] = 1;
        for(reg int i = 2; i < maxn; i ++) rev[i] = ((1ll*(-mod/i) * 1ll*rev[mod%i]) %mod + mod) % mod;
        jc[0] = 1;
        for(reg int i = 1; i < maxn; i ++) jc[i] = 1ll*jc[i-1]*i % mod;
}

int main(){
        freopen("gcd.in", "r", stdin);
        freopen("gcd.out", "w", stdout);
        Init();
        N = read(); M = read(); K = read();
        for(reg int i = 1; i <= N; i ++) A[i] = read();
        for(reg int d = 1; d <= M; d ++){
                x = 0;
                for(reg int i = 1; i <= N; i ++) x += ((A[i]%d) != 0);
                if(x > K){ Ans[d] = 0; continue ; }
                int tmp_1 = KSM(M/d, x), tmp_2 = C(N, N-x), tmp_3 = KSM(M/d-1, K-x);
                tmp[d] = (1ll*tmp_1*tmp_2%mod)*1ll*tmp_3 % mod;
        }
        for(reg int d = 1; d <= M; d ++){
                Ans[d] = tmp[d];
                for(reg int i = 2; i*d <= M; i ++) Ans[d] = ((Ans[d] - tmp[i*d])%mod + mod) % mod;
                printf("%d\n", Ans[d]);
        }
        return 0;
}