当前位置: 首页 > news >正文

[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  (1t1e4)组测试数据.每组测试数据输入一个整数 x    ( 1 ≤ x ≤ 1 e 9 ) x\ \ (1\leq x\leq 1\mathrm{e}9) x  (1x1e9).

思路I

注意到 1111 = 11 ⋅ 100 + 11 , 11111 = 111 ⋅ 100 + 11 1111=11\cdot 100+11,11111=111\cdot 100+11 1111=11100+11,11111=111100+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  (0d<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) (x111d)能否被 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 nmnm.

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) (rl)次.考察过程中 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  (1t1e4)组测试数据.每组测试数据输入两个整数 l , r    ( 1 ≤ l ≤ r ≤ 1 e 9 ) l,r\ \ (1\leq l\leq r\leq 1\mathrm{e}9) l,r  (1lr1e9).进行上述操作,求过程中变化的数码的个数之和.

思路

①倒数第一位的变化个数为 r − l r-l rl.

②令 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 10r10l.

重复上述操作,不断除以 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  (1t1e5)组测试数据.每组测试数据输入三个整数 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  (1n,a,b1e9).若 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+ybnax  (mod b),nax,枚举 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. xi的最小的正整数 x x x.给定正整数 n n n,求 ∑ i = 1 n f ( i ) \displaystyle \sum_{i=1}^n f(i) i=1nf(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  (1t1e4)组测试数据.每组测试数据输入一个整数 n    ( 1 ≤ n ≤ 1 e 16 ) n\ \ (1\leq n\leq 1\mathrm{e}16) n  (1n1e16).

思路

f ( n ) = i f(n)=i f(n)=i,则 1 , ⋯   , ( i − 1 ) ∣ n 1,\cdots,(i-1)\mid n 1,,(i1)n,进而 n ≥ l c m ( 1 , ⋯   , i − 1 ) n\geq \mathrm{lcm}(1,\cdots,i-1) nlcm(1,,i1),这表明 f ( n ) f(n) f(n)不会太大.事实上, n ≤ 1 e 16 n\leq 1\mathrm{e}16 n1e16时, 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,,i1)nlcm(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=i2i(lcm(1,,i1)nlcm(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(nlcm(1,,2)n)+3(lcm(1,,2)nlcm(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 =i1lcm(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 1i1<<ikn;②令 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  (1t1e4)组测试数据.每组测试数据第一行输入一个整数 n    ( 1 ≤ n ≤ 2 e 5 ) n\ \ (1\leq n\leq 2\mathrm{e}5) n  (1n2e5).第二行输入 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  (0ai<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  (1t1e4)组测试数据.每组测试数据第一行输入一个整数 n    ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n  (1n1e5).第二行输入 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  (1ai1e9).数据保证所有测试数据的 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  (2xi+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  (1t1e5)组测试数据.每组测试数据输入两个偶数 x , y    ( 2 ≤ x , y ≤ 1 e 9 ) x,y\ \ (2\leq x,y\leq 1\mathrm{e}9) x,y  (2x,y1e9).

思路

(1)若 x > y x>y x>y,可取 n = x + y n=x+y n=x+y.

(2)若 x ≤ y x\leq y xy,

​ ① n ≥ x n\geq x nx.

​ [] 若 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 ny.

​ [] 若 n > y n>y n>y,则 y   m o d   n = y ≥ x y\ \mathrm{mod}\ n=y\geq x y mod n=yx,而 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 xny表示 n n n [ p , y ] [p,y] [p,y]的中点,即 y − y   m o d   x 2 y-\dfrac{y\ \mathrm{mod}\ x}{2} y2y 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<<an9).有编号 1 ∼ n 1\sim n 1n 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,n1]种面额的数量不超过 1 0 a i + 1 1 0 a i − 1 \dfrac{10^{a_{i+1}}}{10^{a_i}}-1 10ai10ai+11.

下面求最小的 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,k1;② i + e k ≤ n i+ek\leq n i+ekn;③ 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  (1t1e4)组测试数据.每组测试数据第一行输入两个整数 n , e    ( 1 ≤ e ≤ n ≤ 2 e 5 ) n,e\ \ (1\leq e\leq n\leq 2\mathrm{e}5) n,e  (1en2e5).第二行输入 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  (1ai1e9).数据保证所有测试数据的 n n n之和不超过 2 e 5 2\mathrm{e}5 2e5.

思路

m m m个正整数之积是素数当且仅当其中 ( m − 1 ) (m-1) (m1)个数为 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();
}


相关文章:

  • 基于JAVA火车订票系统计算机毕业设计源码+数据库+lw文档+系统+部署
  • 【CSDN:国庆活动】——blink动态里的学习成长
  • SpringBoot+Vue项目计算机等级考试报名系统
  • 【Flink 实战系列】Flink 消费多个 Topic 数据利用侧流输出完成分流功能
  • 【前端工程化】理解和配置process.env.NODE_ENV,项目中的环境变量到底是个啥
  • CVPR 2022 Oral 大连理工提出的SCI 快速、超强的低光照图像增强方法 亲测效果
  • cuda remove
  • CSS进阶篇——更多选择器 (selectors)
  • 嵌入式-ESP32
  • matplotlib绘制直方图,饼图,散点图,气泡图,箱型图,雷达图
  • JDBC编程六步、IDEA开发的第一个JDBC程序
  • 强化学习——day35 读论文:基于深度强化学习的网约车动态路径规划
  • 【408计算机组成原理】—原码、反码、补码、移码(六)
  • Vue入门【九】-- 动态路由和嵌套路由
  • Python数据类型:序列(列表list、元组tuple)
  • 【跃迁之路】【733天】程序员高效学习方法论探索系列(实验阶段490-2019.2.23)...
  • DOM的那些事
  • Java读取Properties文件的六种方法
  • JS专题之继承
  • Laravel Mix运行时关于es2015报错解决方案
  • Phpstorm怎样批量删除空行?
  • Protobuf3语言指南
  • Spring Boot MyBatis配置多种数据库
  • vue-loader 源码解析系列之 selector
  • 读懂package.json -- 依赖管理
  • 高程读书笔记 第六章 面向对象程序设计
  • 回流、重绘及其优化
  • 模型微调
  • 七牛云假注销小指南
  • 如何在 Tornado 中实现 Middleware
  • 它承受着该等级不该有的简单, leetcode 564 寻找最近的回文数
  • 我看到的前端
  • 学习JavaScript数据结构与算法 — 树
  • 移动端 h5开发相关内容总结(三)
  • ​决定德拉瓦州地区版图的关键历史事件
  • #NOIP 2014# day.2 T2 寻找道路
  • (day 12)JavaScript学习笔记(数组3)
  • (LNMP) How To Install Linux, nginx, MySQL, PHP
  • (八)五种元启发算法(DBO、LO、SWO、COA、LSO、KOA、GRO)求解无人机路径规划MATLAB
  • (第一天)包装对象、作用域、创建对象
  • (附源码)spring boot校园拼车微信小程序 毕业设计 091617
  • (六)Hibernate的二级缓存
  • (牛客腾讯思维编程题)编码编码分组打印下标题目分析
  • (七)MySQL是如何将LRU链表的使用性能优化到极致的?
  • (十)DDRC架构组成、效率Efficiency及功能实现
  • (十五)devops持续集成开发——jenkins流水线构建策略配置及触发器的使用
  • (淘宝无限适配)手机端rem布局详解(转载非原创)
  • (五)网络优化与超参数选择--九五小庞
  • (一)appium-desktop定位元素原理
  • (转)四层和七层负载均衡的区别
  • (转载)深入super,看Python如何解决钻石继承难题
  • .cfg\.dat\.mak(持续补充)
  • .NET CF命令行调试器MDbg入门(一)
  • .Net+SQL Server企业应用性能优化笔记4——精确查找瓶颈
  • [ C++ ] STL---string类的模拟实现