JZOJ – 5796 划分

Time Limit : 500ms
Memory Limit : 64MB

Description

有一个未知的序列 $ x $，长度为 $ n $ 。它的 $ K $-划分序列 $ y$ 指的是每连续 $ K$ 个数的和得到划分序列。
$ y[1]=x[1]+x[2]+ \cdots +x[K] , y[2]=x[K+1]+x[K+2]+ \cdots +x[K+K]\cdots $若 $ n $ 不被 $ K $ 整除，则 $ y[n/K+1] $ 可以由少于 $ K $ 个数加起来。比如 $ n=13 $ ，$ K=5 $，则$ y[1]=x[1]+…+x[5] $，$ y[2]=x[6]+….+x[10] $ ，$ y[3]=x[11]+x[12]+x[13] $ 。若小A只确定 $ x $ 的$ K[1] $ 划分序列以及 $ K[2] $ 划分序列…. $ K[M] $ 划分序列的值情况下，问她可以确定 $ x $ 多少个元素的值。

Input

第一行输入两个正整数 $ n $，$ M $。
第二行输入 $ M $ 个正整数表示 $ K[1],K[2]…..K[M] $。

Output

输出1个整数，表示能确定的元素

Sample Input

Case 1

3 1
2

Case 2

6 2
2 3

Case 3

123456789 3
5 6 9

Sample Output

Case 1

1

Case 2

2

Case 3

10973937

Data Constraint

对于20%的数据，$ 3 \leq N \leq 2000,M \leq 3 $。
对于40%的数据，$ 3 \leq N \leq 5 \times 10^6 $。
对于100%的数据，$ 3 \leq N \leq 10^9 , 1 \leq M \leq 10，2 \leq K[i] < N $。

解题思路

我们先思考一个数字 $ P $ 在什么情况下能够被确定

非常显然，$ P \ mod \ k[i]=0 $, $ p \ mod \ k[j]=1 $ 的时候数字 $ P $ 能够被确定

那么

$$p=a1 \times k[i]=a2 \times k[j]+1 $$

$$a1 \times k[i]-a2 \times k[j]=1 $$

我们可以用扩展欧几里得求出有多少个解

但是这样可能会有重复的情况发生，我们考虑容斥

对于一些方程

$$
\begin{cases}
P \ mod \ k[i_1]=0 & \\
P \ mod \ k[i_2]=0 & \\
P \ mod \ k[i_3]=0 & \\
P \ mod \ k[j_1]=1 & \\
P \ mod \ k[j_2]=1 & \\
P \ mod \ k[j_3]=1 &
\end{cases}
$$

实际上等价于

$$
\begin{cases}
P \ mod \ lcm(k[i_1],k[i_2],…)=0 & \\
P \ mod \ lcm(k[j_1],k[j_2],…)=1 &
\end{cases}
$$

我们将他们分别命名为 $ a $ 和 $ b $
要求 $ xa – yb = 1 $

我们可以求出 $ x $ 的通解为 $ x = x_0 + kb $

只需要求出 $ k+1 $ 即为这个方程的解的个数

移项即可得到 $ k+1 = \frac{\frac{n}{a}-x_0+b}{b} $

容斥系数为 $ (-1)^{|a| + |b|} $ (加入 $ i $ 集的 $ k $的个数为 $ |a| $，加入 $ j $ 集的为 $ |b| $)

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 20 + 10;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

inline long long exgcd(long long a, long long b, long long &x, long long &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }else{
        long long d = exgcd(b, a%b, y, x);
        y -= x * (a / b);
        return d;
    }
}

inline long long gcd(long long a, long long b){
    if(b == 0)
        return a;
    return gcd(b, a%b);
}

inline long long lcm(long long a, long long b){
    if(!a)
        return b;
    if(!b)
        return a;

    return a / gcd(a, b) * b;
}

int data[MAXN];
int n, m;
long long ans;

inline void solve(int x, long long a, long long b, int k){
    if(a > n || b > n)
        return;

    if(x == m + 1){
        if(!a || !b)
            return;

        long long x, y;
        long long d = exgcd(a, b, x, y);

        if(d != 1)
            return;

        x %= b;

        while(x <= 0)
            x += b;


        if(k%2 == 0)
            ans += (n/a - x + b) / b;
        else
            ans -= (n/a - x + b) / b;

        return;
    }

    solve(x+1, lcm(a, data[x]), b, k+1);
    solve(x+1, a, lcm(b, data[x]), k+1);
    solve(x+1, a, b, k);
}

int main(){

    freopen("sazetak.in", "r", stdin);
    freopen("sazetak.out", "w", stdout);

    n = read();
    m = read();

    for(register int i=1; i<=m; i++)
        data[i] = read();

    data[++m] = n;

    solve(1, 0, 0, 0);

    printf("%lld", ans);
    return 0;
}