题面

有一个未知的序列 x，长度为 n。它的 K-划分序列 y 指的是每连续 K 个数的和得到划 分序列，y[1]=x[1]+x[2]+....+x[K]，y[2]=x[K+1]+x[K+2]+....+x[K+K]....。 若 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 多少个元素的值。

输入格式

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

输出格式

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

Sample datas

sample input #1

3 1
2

sample output #1

1

sample input #2

6 2
2 3

sample output #2

2

sample input #3

123456789 3
5 6 9

sample output #3

10973937

sample input #4

4833827 4
7 8 9 10

sample output #4

552436

【样例解释】

【样例 1 解释】

小 A 知道 x 的 2-划分序列，即分别知道 x[1]+x[2]，x[3]的值。

小 A 可以知道 x[3]的值。

【样例 2 解释】

小 A 知道 x 的 2-划分序列，即分别知道 x[1]+x[2]，x[3]+x[4]，x[5]+x[6] 的值。

小 A 知道 x 的 3-划分序列，即分别知道 x[1]+x[2]+x[3] ，x[4]+x[5]+x[6] 的值。

小 A 可以知道 x[3],x[4]的值，个数为 2.

【数据范围】

对于 20%的数据，3 ≤ 𝑁 ≤ 2000, 𝑀 ≤ 3。 对于 40%的数据，3 ≤ 𝑁 ≤ 5 ∗ 10^6。 对于 100%的数据，3 ≤ 𝑁 ≤ 10^9, 1 ≤ 𝑀 ≤ 10，2 ≤ 𝐾[𝑖] < 𝑁。

题解

（真毒瘤的错误）

实际上给你一个K-划分是告诉你了前 k 个(sum[k])、前 2k 个(sum[2k])、前 3k 个(sum[3k])……的前缀和sum分别是多少，

而且我们知道，在只知道前缀和数组sum的前提下，你要知道原本的第 i 个位置的数字，当且仅当知道了 sum[i] 和 sum[i-1] 然后相减所得，没有别的方法可以得到它，就算你知道其它所有的 sum[] 是多少，没那两个你也是算不出来的。

因此，渐渐就有思路了。

当你新得到一个 a[i] 时（即原题中的 K[i] 大写字母打着有些麻烦，就习惯地用 a[i] 了 ），你得计算 a[i] 贡献，

a[i] 的贡献就两种：

1. x 为 a[i] 的倍数，sum[x] 原本不知道，sum[x+1]原本知道，此时的 x+1 应加入贡献
2. x 为 a[i] 的倍数，sum[x] 原本不知道，sum[x -1]原本知道，此时的   x   应加入贡献

我们设上面两句话的 x 为 k*a[i]，则 k 分别要满足的条件为：

1. （初中的同学看过来：“” 是 “存在” 的意思，即存在一个小于 i 的 j，满足...，“” 是 “任意” 的意思，即对于任意的小于 i 的 j，满足...，大括号内两个条件要同时满足）
2. 

我们知道，对于每个 j < i ，如果分别求满足上述条件的 k 的数量，显然大概率会算重，而且并不是上面两个式子应有的解法，

但是，这样求又是最快的，怎么办呢，用容斥！

我们把大括号内两个条件分开，再把对于每个 j 的条件分开，一共得到 2 * (i-1) 个条件，然后枚举  种状态做容斥，下面那个 “  ” 的式子，就可以把它变成 “  ”的式子来算，这样更方便容斥。

对于只有一个条件的状态，我们很好算，但是对于很多条件的状态就显得困难，不急，我们继续推

上述两个大括号可以等价于：

1. 
2. 

把一些条件单独拿出来就是这样的形式：

这是个线性同余方程组，我们可以用扩展中国剩余定理来做，

最后求得了一个方程：

k 的数量就可以直接做除法了！

把两个大括号分别求贡献，

由于我用记忆化处理每个状态，每次算一个状态就只用算一次式子合并，时间复杂度（自己证一下吧）

CODE

记忆化直接递归，白爆60分，呜呼！

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 15
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) ((-x)&(x))
#pragma GCC optimize(2)
LL read() {LL f = 1,x = 0;char s = getchar();while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
LL a[MAXN];
LL gcd(LL a,LL b) {return b==0 ? a:gcd(b,a%b);}
LL exgcd(LL a,LL b,LL &x,LL &y) {if(b == 0) {x = 1;y = 0;return a;}LL r = exgcd(b,a%b,y,x);y -= x*(a/b);return r;
}
struct sz{LL a,b; sz(){a=b=0;}sz(LL A,LL B){a=A;b=B;}
}dp1[1<<10|5],dp2[1<<10|5];
sz merg(sz x,sz y) {if(x.b == 0 || y.b == 0) return sz();if(x.a > y.a) swap(x,y);if(x.b > n) {if(x.a % y.b == y.a) return x;else return sz();}if(y.b > n) {if(y.a % x.b == x.a) return y;else return sz();}LL k1,k2,re = y.a - x.a;LL gc = exgcd(x.b,y.b,k1,k2);LL lc = x.b / gc * y.b;if(re % gc) return sz();k1 *= re / gc;sz as = sz((x.a + x.b*k1) % lc,lc);if(as.a<0) as.a+=as.b;if(as.a > n) return sz();return as;
}
int f1[1<<10|5],f2[1<<10|5],ct[1<<10|5];
sz DP1(int x) {if(f1[x]) return dp1[x];f1[x] = 1;return (dp1[x] = merg(DP1(x-lowbit(x)),DP1(lowbit(x))));// 您可想过，这里曾是 return merg(DP1(x-lowbit(x)),DP1(lowbit(x))); ？
}
sz DP2(int x) {if(f2[x]) return dp2[x];f2[x] = 1;return (dp2[x] = merg(DP2(x-lowbit(x)),DP2(lowbit(x))));
}
int ANS1(sz s,int ai) {int as = (((n-1)/ai) - s.a) / s.b + 1;if(s.a == 0) as --;return as;
}
int ANS2(sz s,int ai) {int as = ((n/ai) - s.a) / s.b + 1;if(s.a == 0) as --;return as;
}
int main() {n = read();m = read();for(int i = 1;i < 1024;i ++) ct[i] = ct[i-lowbit(i)] + 1;int ans = 0;bool flag = 1,flag2 = 0;for(int i = 1;i <= m;i ++) {a[i] = read();
//		printf("a[%d]=%d : \n",i,a[i]);bool fl = 0;for(int j = 1;j < i;j ++) {if(a[i] % a[j] == 0) fl = 1;}if(fl) {i --;m --;continue;}memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));f1[0] = 1;dp1[0] = sz(0,1);int tp = (1<<(i-1))-1;for(int j = 1;j < i;j ++) {//k*ai ≡-1 (\mod aj)int gc;if((gc=gcd(a[i],a[j])) == 1) {LL x,y;exgcd(a[i],a[j],x,y);x = (a[j] - x % a[j]) % a[j];dp2[1<<(j-1)] = sz(x,a[j]);}else dp2[1<<(j-1)] = sz();f2[1<<(j-1)] = 1;dp1[1<<(j-1)] = sz(0,a[j]/gc);f1[1<<(j-1)] = 1;
//			printf("dp1[%d]=%d(%d)  dp2[%d]=%d(%d)\n",j,dp1[1<<(j-1)].a,dp1[1<<(j-1)].b,j,dp2[1<<(j-1)].a,dp2[1<<(j-1)].b);}LL as = 0;for(int k2 = 1;k2 <= tp;k2 ++) {for(int k1 = 0;k1 <= tp;k1 ++) {sz res = merg(DP1(k1),DP2(k2));
//				if(k1 == 6) printf("( [%d%d]:%d(mod %d) )\n",k1,k2,res.a,res.b);if(res.b == 0 || res.a > (n-1)/a[i]) continue;if((ct[k1]+ct[k2])&1) (as += ANS1(res,a[i])) %= MOD;else (((as -= ANS1(res,a[i])) %= MOD) += MOD) %= MOD;
//				printf("[%d%d]:%d(mod %d)\n",k1,k2,res.a,res.b);}}(ans += as) %= MOD;
//		printf("%d\n",ans);memset(f2,0,sizeof(f2));for(int j = 1;j < i;j ++) {if(gcd(a[i],a[j]) == 1) {LL x,y;exgcd(a[i],a[j],x,y);x = (x % a[j] + a[j]) % a[j];dp2[1<<(j-1)] = sz(x,a[j]);}else dp2[1<<(j-1)] = sz();f2[1<<(j-1)] = 1;
//			printf("dp2[%d]=%d(%d)\n",j,dp2[1<<(j-1)].a,dp2[1<<(j-1)].b);}as = 0;for(int k2 = 1;k2 <= tp;k2 ++) {for(int k1 = 0;k1 <= tp;k1 ++) {sz res = merg(DP1(k1),DP2(k2));
//				if(k1 == 6) printf("( [%d%d]:%d(mod %d) %d(mod %d))\n",k1,k2,d1.a,d1.b,d2.a,d2.b);if(res.b == 0 || res.a > n/a[i]) continue;if((ct[k1]+ct[k2])&1) (as += ANS2(res,a[i])) %= MOD;else (((as -= ANS2(res,a[i])) %= MOD) += MOD) %= MOD;
//				printf("[%d%d]:%d(mod %d)\n",k1,k2,res.a,res.b);}}(ans += as) %= MOD;
//		printf("%d\n",ans);}for(int i = 1;i <= m;i ++) {if(n % a[i] == 0) flag = 0;if((n-1) % a[i] == 0) flag2 = 1;}if(flag && flag2) ans ++;printf("%d\n",ans);return 0;
}