P84463

贴吧 82 号

难度 未定
讨论 统计 3通过 5提交 60%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

小 Z 在贴吧上刷到了个帖子,编号 82。

他看不懂,但他大受震撼,所以他决定把这份愤怒转化为一道 OI 题。

给定一个长度为 n 的 \texttt{01} 字符串 s(下标从 1 开始)。

你可以进行若干次操作,每次操作选择一个正整数 x(1 \le x \le n),然后将所有下标是 x 的倍数的位置上的字符取反(即 \texttt{0} 变成 \texttt{1},\texttt{1} 变成 \texttt{0})。

请问,最少需要多少次操作,才能将整个字符串变成全 \texttt{1} 的字符串?

输入

第一行,输入一个整数 n,表示字符串长度。

第二行,输入一个长度为 n 的字符串 s,保证 s 只包含字符 \texttt{0} 和 \texttt{1}。

输出

输出共一行,一个整数,表示最少操作次数。

样例

样例 1
输入
4
1010
输出
1
样例 2
输入
2
01
输出
2
样例 3
输入
3
000
输出
1

提示

样例 #1

选择 x = 2,将位置 2,4 取反,得到 \texttt{1111},共 1 次操作。

数据范围

本题采用捆绑测试。

  • 子任务 0(10 分):n \le 10;
  • 子任务 1(30 分):n \le 10^3;
  • 子任务 2(10 分):字符串 s 只由 \texttt{0} 构成或只由 \texttt{1} 构成;
  • 子任务 3(50 分):无特殊限制;

对于 100\% 的数据,1 \le n \le 10^5,字符串仅由 \texttt{0} 和 \texttt{1} 组成。

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交