[Codeforces] number theory (R1600) Part.11
[Codeforces] number theory (R1600) Part.11
题单:https://codeforces.com/problemset/page/1?tags=number+theory%2C1201-1600
1526B. I Hate 1111
原题指路:https://codeforces.com/problemset/problem/1526/B
题意
给定一个整数 x x x,问 x x x能否表示为 11 , 111 , 1111 , ⋯ 11,111,1111,\cdots 11,111,1111,⋯的线性组合,若能则输出"YES";否则输出"NO".
有 t ( 1 ≤ t ≤ 1 e 4 ) t\ \ (1\leq t\leq 1\mathrm{e}4) t (1≤t≤1e4)组测试数据.每组测试数据输入一个整数 x ( 1 ≤ x ≤ 1 e 9 ) x\ \ (1\leq x\leq 1\mathrm{e}9) x (1≤x≤1e9).
思路I
注意到 1111 = 11 ⋅ 100 + 11 , 11111 = 111 ⋅ 100 + 11 1111=11\cdot 100+11,11111=111\cdot 100+11 1111=11⋅100+11,11111=111⋅100+11,故只需判断 x x x能否表示为 11 , 111 11,111 11,111线性组合.
设 x = 11 a + 111 b , b = 11 c + d ( 0 ≤ d < 11 ) x=11a+111b,b=11c+d\ \ (0\leq d<11) x=11a+111b,b=11c+d (0≤d<11),则 x = 11 ( a + 111 c ) + 111 d x=11(a+111c)+111d x=11(a+111c)+111d,遍历所有 d d d,检查 ( x − 111 d ) (x-111d) (x−111d)能否被 11 11 11整除即可.
代码I
void solve() {
int n; cin >> n;
while (true) {
if (n % 11 == 0) {
cout << "YES" << endl;
return;
}
n -= 111;
if (n < 0) {
cout << "NO" << endl;
return;
}
}
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
思路II
[Chicken McNugget定理] 对互素的两正整数 n , m n,m n,m,不能被表示为 n , m n,m n,m的线性组合的最大整数为 n m − n − m nm-n-m nm−n−m.
因 gcd ( 11 , 111 ) = 1 \gcd(11,111)=1 gcd(11,111)=1,则不能表示为 11 , 111 11,111 11,111的线性组合的最大整数位 1099 1099 1099.预处理出 ≤ 1099 \leq 1099 ≤1099的可表示为 11 , 111 11,111 11,111的线性组合的数即可.
1536C. Diluc and Kaeya
原题指路:https://codeforces.com/problemset/problem/1536/C
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个长度为 n n n的只由字符’D’和’K’组成的字符串 s s s.对 s s s的每个非空前缀,问至多能将其分为多少段,使得每一段中’D’的个数与’K’的个数之比相等.
思路
对每个字符串,设其中’D’、'K’的个数分别为 a a a、 b b b.每个前缀的答案即它之前出现过的 ( a gcd ( a , b ) , b gcd ( a , b ) ) \left(\dfrac{a}{\gcd(a,b)},\dfrac{b}{\gcd(a,b)}\right) (gcd(a,b)a,gcd(a,b)b)的个数 + 1 +1 +1.
代码
pii get(int a, int b) {
int g = gcd(a, b);
return { a / g,b / g };
}
void solve() {
int n; string s; cin >> n >> s;
map<pii, int> cnt;
int d = 0, k = 0;
for (auto ch : s) {
if (ch == 'D') d++;
else k++;
cout << ++cnt[get(d, k)] << ' ';
}
cout << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1538F. Interesting Function
原题指路:https://codeforces.com/problemset/problem/1538/F
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定两整数 l , r ( l < r ) l,r\ \ (l<r) l,r (l<r),对 l l l每次 + 1 +1 +1直至 l = r l=r l=r,则需加 ( r − l ) (r-l) (r−l)次.考察过程中 l l l变化的数码的个数,如 l = 909 l=909 l=909,加 1 1 1后 l = 910 l=910 l=910,变化了 2 2 2个数码.显然变化的数码是结果数的某个后缀.
有 t ( 1 ≤ t ≤ 1 e 4 ) t\ \ (1\leq t\leq 1\mathrm{e}4) t (1≤t≤1e4)组测试数据.每组测试数据输入两个整数 l , r ( 1 ≤ l ≤ r ≤ 1 e 9 ) l,r\ \ (1\leq l\leq r\leq 1\mathrm{e}9) l,r (1≤l≤r≤1e9).进行上述操作,求过程中变化的数码的个数之和.
思路
①倒数第一位的变化个数为 r − l r-l r−l.
②令 l = ⌊ l 10 ⌋ , r = ⌊ r 10 ⌋ l=\left\lfloor\dfrac{l}{10}\right\rfloor,r=\left\lfloor\dfrac{r}{10}\right\rfloor l=⌊10l⌋,r=⌊10r⌋,则原本的倒数第二位变为现在的倒数第一位,变化的个数为 ⌊ r 10 ⌋ − ⌊ l 10 ⌋ \left\lfloor\dfrac{r}{10}\right\rfloor-\left\lfloor\dfrac{l}{10}\right\rfloor ⌊10r⌋−⌊10l⌋.
重复上述操作,不断除以 10 10 10下取整,累加答案即可.
代码
void solve() {
int l, r; cin >> l >> r;
int ans = 0;
while (l || r) {
ans += r - l;
l /= 10, r /= 10;
}
cout << ans << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1542B. Plus and Multiply
原题指路:https://codeforces.com/problemset/problem/1542/B
题意 ( 3 s ) (3\ \mathrm{s}) (3 s)
给定两整数 a , b a,b a,b,用如下方式产生一个无限集:① 1 1 1在集合中;②若 x x x在集合中,则 a x ax ax和 x + b x+b x+b也在集合中.
有 t ( 1 ≤ t ≤ 1 e 5 ) t\ \ (1\leq t\leq 1\mathrm{e}5) t (1≤t≤1e5)组测试数据.每组测试数据输入三个整数 n , a , b ( 1 ≤ n , a , b ≤ 1 e 9 ) n,a,b\ \ (1\leq n,a,b\leq 1\mathrm{e}9) n,a,b (1≤n,a,b≤1e9).若 n n n在集合中,输出"YES";否则输出"NO".
思路
有解等价于 n n n能表示为 a x + y b a^x+yb ax+yb.
[证] a x + y b a^x+yb ax+yb乘 a a a得 a x + 1 + y b a^{x+1}+yb ax+1+yb;加 b b b得 a x + ( y + 1 ) b a^x+(y+1)b ax+(y+1)b.由数学归纳法即证.
n = a x + y b ⇔ n ≡ a x ( m o d b ) , n ≥ a x n=a^x+yb\Leftrightarrow n\equiv a^x\ \ (\mathrm{mod}\ b),n\geq a^x n=ax+yb⇔n≡ax (mod b),n≥ax,枚举 a x a^x ax即可.注意特判 a = 1 a=1 a=1的情况.
代码
void solve() {
int a, b, n; cin >> n >> a >> b;
if (a == 1) cout << ((n - 1) % b ? "NO" : "YES") << endl;
else {
for (ll i = 1; i <= n; i *= a) {
if (i % b == n % b) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1542C. Strange Function
原题指路:https://codeforces.com/problemset/problem/1542/C
题意
定义 f ( i ) f(i) f(i)为 s . t . x ∤ i \ s.t.\ x\not\mid i s.t. x∣i的最小的正整数 x x x.给定正整数 n n n,求 ∑ i = 1 n f ( i ) \displaystyle \sum_{i=1}^n f(i) i=1∑nf(i),答案对 1 e 9 + 7 1\mathrm{e}9+7 1e9+7取模.
有 t ( 1 ≤ t ≤ 1 e 4 ) t\ \ (1\leq t\leq 1\mathrm{e}4) t (1≤t≤1e4)组测试数据.每组测试数据输入一个整数 n ( 1 ≤ n ≤ 1 e 16 ) n\ \ (1\leq n\leq 1\mathrm{e}16) n (1≤n≤1e16).
思路
若 f ( n ) = i f(n)=i f(n)=i,则 1 , ⋯ , ( i − 1 ) ∣ n 1,\cdots,(i-1)\mid n 1,⋯,(i−1)∣n,进而 n ≥ l c m ( 1 , ⋯ , i − 1 ) n\geq \mathrm{lcm}(1,\cdots,i-1) n≥lcm(1,⋯,i−1),这表明 f ( n ) f(n) f(n)不会太大.事实上, n ≤ 1 e 16 n\leq 1\mathrm{e}16 n≤1e16时, f ( n ) ≤ 100 f(n)\leq 100 f(n)≤100.
使得 f ( k ) = i f(k)=i f(k)=i的 k k k的个数为 ⌊ n l c m ( 1 , ⋯ , i − 1 ) ⌋ − ⌊ n l c m ( 1 , ⋯ , i ) ⌋ \left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,i-1)}\right\rfloor-\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,i)}\right\rfloor ⌊lcm(1,⋯,i−1)n⌋−⌊lcm(1,⋯,i)n⌋,
则 a n s = ∑ i ≥ 2 i ⋅ ( ⌊ n l c m ( 1 , ⋯ , i − 1 ) ⌋ − ⌊ n l c m ( 1 , ⋯ , i ) ⌋ ) \displaystyle ans=\sum_{i\geq 2}i\cdot\left(\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,i-1)}\right\rfloor-\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,i)}\right\rfloor\right) ans=i≥2∑i⋅(⌊lcm(1,⋯,i−1)n⌋−⌊lcm(1,⋯,i)n⌋)
= 2 ( n − ⌊ n l c m ( 1 , ⋯ , 2 ) ⌋ ) + 3 ( ⌊ n l c m ( 1 , ⋯ , 2 ) − ⌊ n l c m ( 1 , ⋯ , 3 ) ⌋ ⌋ ) + . . . =2\left(n-\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,2)}\right\rfloor\right)+3\left(\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,2)}-\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,3)}\right\rfloor\right\rfloor\right)+... =2(n−⌊lcm(1,⋯,2)n⌋)+3(⌊lcm(1,⋯,2)n−⌊lcm(1,⋯,3)n⌋⌋)+...
= ∑ i ≥ 1 ⌊ n l c m ( 1 , ⋯ , i ) ⌋ + n \displaystyle =\sum_{i\geq 1}\left\lfloor\dfrac{n}{\mathrm{lcm}(1,\cdots,i)}\right\rfloor+n =i≥1∑⌊lcm(1,⋯,i)n⌋+n.
代码
const int MOD = 1e9 + 7;
void solve() {
ll n; cin >> n;
ll l = 1; // lcm
int ans = n % MOD; // 注意模
for (int i = 1; l <= n; i++) {
l = lcm(l, i);
ans = ((ll)ans + n / l) % MOD;
}
cout << ans << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1601A. Array Elimination
原题指路:https://codeforces.com/problemset/problem/1601/A
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个长度为 n n n的序列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an.选定一个整数 k ∈ [ 1 , n ] k\in[1,n] k∈[1,n],现有操作,分为如下三步:①选择 k k k个相异的下标 1 ≤ i 1 < ⋯ < i k ≤ n 1\leq i_1<\cdots<i_k\leq n 1≤i1<⋯<ik≤n;②令 x = a i 1 & ⋯ & a i k x=a_{i_1}\& \cdots\& a_{i_k} x=ai1&⋯&aik;③令 a i 1 − = x , ⋯ , a i k − = x a_{i_1}-=x,\cdots,a_{i_k}-=x ai1−=x,⋯,aik−=x.求所有的 k k k,使得若干次操作后 a [ ] a[] a[]中的元素都变为 0 0 0,升序输出所有 k k k.可以证明至少存在一个 k k k.
有 t ( 1 ≤ t ≤ 1 e 4 ) t\ \ (1\leq t\leq 1\mathrm{e}4) t (1≤t≤1e4)组测试数据.每组测试数据第一行输入一个整数 n ( 1 ≤ n ≤ 2 e 5 ) n\ \ (1\leq n\leq 2\mathrm{e}5) n (1≤n≤2e5).第二行输入 n n n个整数 a 1 , ⋯ , a n ( 0 ≤ a i < 2 30 ) a_1,\cdots,a_n\ \ (0\leq a_i<2^{30}) a1,⋯,an (0≤ai<230).数据保证所有测试数据的 n n n之和不超过 2 e 5 2\mathrm{e}5 2e5.
思路
显然每次操作只影响所有 a i a_i ai的二进制表示的某个数位.设某个数位上有 x x x个数为 1 1 1,注意到一次操作只能改变 k k k个或 0 0 0个 1 1 1,故合法的 k k k是所有 a i a_i ai的二进制表示的每个数位的 1 1 1的个数的 gcd \gcd gcd的约数,枚举约数即可.
注意特判所有数都为 0 0 0的情况.
代码
void solve() {
int n; cin >> n;
vi cnt(30); // a_i的二进制表示的每个数位上1的个数
for (int i = 0; i < n; i++) {
int a; cin >> a;
for (int j = 0; j < 31; j++)
if (a >> j & 1) cnt[j]++;
}
int g = 0;
for (auto i : cnt) g = gcd(g, i);
if (!g) // 注意特判
for (int i = 1; i <= n; i++) cout << i << " \n"[i == n];
else {
vi ans;
for (int i = 1; (ll)i * i <= g; i++) {
if (g % i == 0) {
ans.push_back(i);
if (i != g / i) ans.push_back(g / i);
}
}
sort(all(ans));
for (auto i : ans) cout << i << ' ';
cout << endl;
}
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1603A. Di-visible Confusion
原题指路:https://codeforces.com/problemset/problem/1603/A
题意
给定一个长度为 n n n的序列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an.设序列 a [ ] a[] a[]的长度为 ∣ a ∣ |a| ∣a∣,现有操作:选择一个下标 i ∈ [ 1 , ∣ a ∣ ] s . t . ( i + 1 ) ∤ a i i\in [1,|a|]\ s.t.\ (i+1)\not\mid a_i i∈[1,∣a∣] s.t. (i+1)∣ai,删除 a i a_i ai,剩下的 a [ ] a[] a[]重新编号.问能否删除序列的所有元素,若能则输出"YES";否则输出"NO".
有 t ( 1 ≤ t ≤ 1 e 4 ) t\ \ (1\leq t\leq 1\mathrm{e}4) t (1≤t≤1e4)组测试数据.每组测试数据第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5).第二行输入 n n n个整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (1≤ai≤1e9).数据保证所有测试数据的 n n n之和不超过 3 e 5 3\mathrm{e}5 3e5.
思路
若 a i a_i ai不能被删除,则 a i m o d x = 0 ( 2 ≤ x ≤ i + 1 ) a_i\ \mathrm{mod}\ x=0\ \ (2\leq x\leq i+1) ai mod x=0 (2≤x≤i+1),即 l c m ( 2 , ⋯ , i + 1 ) ∣ a i \mathrm{lcm}(2,\cdots,i+1)\mid a_i lcm(2,⋯,i+1)∣ai.注意到 l c m ( 2 , ⋯ , 23 ) > 1 e 9 \mathrm{lcm}(2,\cdots,23)>1\mathrm{e}9 lcm(2,⋯,23)>1e9,故对每个 a i a_i ai,至多只需枚举 22 22 22个 i i i,时间复杂度 O ( 22 n ) O(22n) O(22n),可过.
代码
void solve() {
int n; cin >> n;
vi a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
bool ok = false;
for (int j = 1; j <= i; j++) {
if (a[i] % (j + 1)) {
ok = true;
break;
}
}
if (!ok) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1603B. Moderate Modular Mode
原题指路:https://codeforces.com/problemset/problem/1603/B
题意
给定两个偶数 x , y x,y x,y,求一个整数 n ∈ [ 1 , 2 e 18 ] s . t . n m o d x = y m o d n n\in[1,2\mathrm{e}18]\ s.t.\ n\ \mathrm{mod}\ x=y\ \mathrm{mod}\ n n∈[1,2e18] s.t. n mod x=y mod n.可以证明一定有解.
有 t ( 1 ≤ t ≤ 1 e 5 ) t\ \ (1\leq t\leq 1\mathrm{e}5) t (1≤t≤1e5)组测试数据.每组测试数据输入两个偶数 x , y ( 2 ≤ x , y ≤ 1 e 9 ) x,y\ \ (2\leq x,y\leq 1\mathrm{e}9) x,y (2≤x,y≤1e9).
思路
(1)若 x > y x>y x>y,可取 n = x + y n=x+y n=x+y.
(2)若 x ≤ y x\leq y x≤y,
① n ≥ x n\geq x n≥x.
[证] 若 n < x n<x n<x,则 n m o d x = n n\ \mathrm{mod}\ x=n n mod x=n,而 y m o d n < n y\ \mathrm{mod}\ n<n y mod n<n,矛盾.
② n ≤ y n\leq y n≤y.
[证] 若 n > y n>y n>y,则 y m o d n = y ≥ x y\ \mathrm{mod}\ n=y\geq x y mod n=y≥x,而 n m o d x n\ \mathrm{mod}\ x n mod x,矛盾.
③如下图,假设初始时你在 x = 0 x=0 x=0处,准备以步长 x x x跳到 x = y x=y x=y处.
显然存在一个点$x=p=y-(y\ \mathrm{mod}\ x)\ s.t.\ 再多跳一步就超过 再多跳一步就超过 再多跳一步就超过x=y . 因 .因 .因x,y 是偶数 , 则 是偶数,则 是偶数,则p$是偶数.
n m o d x = y m o d n n\ \mathrm{mod}\ x=y\ \mathrm{mod}\ n n mod x=y mod n且 x ≤ n ≤ y x\leq n\leq y x≤n≤y表示 n n n是 [ p , y ] [p,y] [p,y]的中点,即 y − y m o d x 2 y-\dfrac{y\ \mathrm{mod}\ x}{2} y−2y mod x.
代码
void solve() {
int x, y; cin >> x >> y;
cout << (x > y ? x + y : y - y % x / 2) << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1606C. Banknotes
原题指路:https://codeforces.com/problemset/problem/1606/C
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个长度为 n n n的序列 a 1 , ⋯ , a n ( 0 = a 1 < a 2 < ⋯ < a n ≤ 9 ) a_1,\cdots,a_n\ \ (0=a_1<a_2<\cdots<a_n\leq 9) a1,⋯,an (0=a1<a2<⋯<an≤9).有编号 1 ∼ n 1\sim n 1∼n的 n n n种面额的货币,其中第 i i i种的面额为 1 0 a i 10^{a_i} 10ai.定义 f ( s ) f(s) f(s)为表示 s s s元所需的最少货币数.给定一个整数 k k k,求 k k k张货币不能表示出的最小面额 s s s,即最小的 s s . t . f ( s ) > k s\ s.t.\ f(s)>k s s.t. f(s)>k.
思路
为求 f ( s ) f(s) f(s),应从大到小枚举面额,第 i i i种面额所需的数量为 ⌊ s 1 0 a i ⌋ \left\lfloor\dfrac{s}{10^{a_i}}\right\rfloor ⌊10ais⌋,并令 s % = 1 0 a i s\%=10^{a_i} s%=10ai.此时因 s < 1 0 a i s<10^{a_i} s<10ai,则所需的第 i ∈ [ 1 , n − 1 ] i\in [1,n-1] i∈[1,n−1]种面额的数量不超过 1 0 a i + 1 1 0 a i − 1 \dfrac{10^{a_{i+1}}}{10^{a_i}}-1 10ai10ai+1−1.
下面求最小的 s s . t . f ( s ) > k s\ s.t.\ f(s)>k s s.t. f(s)>k.设 l e f t left left表示还剩下多少货币可以拿,因 f ( s ) ≥ k + 1 f(s)\geq k+1 f(s)≥k+1,故 l e f t left left初始值为 k + 1 k+1 k+1.从小到大枚举面额,则第 i i i种面额应拿的数量为 min { l e f t , ⌊ s 1 0 a i ⌋ } \min\left\{left,\left\lfloor\dfrac{s}{10^{a_i}}\right\rfloor\right\} min{left,⌊10ais⌋}.
代码
void solve() {
int n, k; cin >> n >> k;
vi a(n);
for (auto& ai : a) {
cin >> ai;
ai = qpow(10, ai);
}
k++; // 注意+1
ll ans = 0;
for (int i = 0; i < n; i++) {
int cnt = k;
if (i + 1 < n) cnt = min(cnt, a[i + 1] / a[i] - 1);
ans += (ll)a[i] * cnt;
k -= cnt;
}
cout << ans << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1609C. Complex Market Analysis
原题指路:https://codeforces.com/problemset/problem/1609/C
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个长度为 n n n的序列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an和一个自然数 e e e.求满足如下条件的整数对 ( i , k ) (i,k) (i,k)的个数:① i , k ≥ 1 i,k\geq 1 i,k≥1;② i + e k ≤ n i+ek\leq n i+ek≤n;③ a i × a i + e × a i + 2 e × ⋯ × a i + k e a_i\times a_{i+e}\times a_{i+2e}\times\cdots\times a_{i+ke} ai×ai+e×ai+2e×⋯×ai+ke是素数.
有 t ( 1 ≤ t ≤ 1 e 4 ) t\ \ (1\leq t\leq 1\mathrm{e}4) t (1≤t≤1e4)组测试数据.每组测试数据第一行输入两个整数 n , e ( 1 ≤ e ≤ n ≤ 2 e 5 ) n,e\ \ (1\leq e\leq n\leq 2\mathrm{e}5) n,e (1≤e≤n≤2e5).第二行输入 n n n个整数 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (1≤ai≤1e9).数据保证所有测试数据的 n n n之和不超过 2 e 5 2\mathrm{e}5 2e5.
思路
m m m个正整数之积是素数当且仅当其中 ( m − 1 ) (m-1) (m−1)个数为 1 1 1,另外一个数为素数.
枚举每个素数,预处理出其左边、右边每隔 e e e个数的 1 1 1的个数 a a a、 b b b,则该素数对答案的贡献为 ( a + 1 ) ( b + 1 ) − 1 (a+1)(b+1)-1 (a+1)(b+1)−1,其中 − 1 -1 −1是因为两边 1 1 1的个数不能同时为 0 0 0.
代码
const int MAXN = 1e6 + 5;
int primes[MAXN], cnt;
bool state[MAXN];
int pre[MAXN], suf[MAXN]; // 记录每个位置的左边、右边每隔e个数的1的个数
void init() {
state[1] = true; // 注意把1也筛掉
for (int i = 2; i < MAXN; i++) {
if (!state[i]) primes[cnt++] = i;
for (int j = 0; primes[j] * i < MAXN; j++) {
state[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void solve() {
int n, e; cin >> n >> e;
vi a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
// 预处理pre[]和suf[]
for (int i = 1; i <= n; i++) {
if (i > e && a[i - e] == 1) pre[i] = pre[i - e] + 1;
else pre[i] = 0;
}
for (int i = n; i; i--) {
if (i + e <= n && a[i + e] == 1) suf[i] = suf[i + e] + 1;
else suf[i] = 0;
}
ll ans = 0;
for (int i = 1; i <= n; i++)
if (!state[a[i]]) ans += (ll)(pre[i] + 1) * (suf[i] + 1) - 1; // 对素数统计答案
cout << ans << endl;
}
int main() {
init();
CaseT // 单测时注释掉该行
solve();
}