题解：P17414 「IXOI R3」贴吧 82 号

· · 题解

本题放在这个位置很合适，具备一定的思维难度，但代码确十分简洁，适合练习思维。

其实本题表面复杂，但深入分析确会发现十分简单。

题目要求我们把整个字符串都变成1，那我们就就可以简单的考虑一下：直接把遇见的所有的0全部都进行一次操作，因为这样就可以把我们遇见的这个0变为1。

这个时候，只能会有人疑惑：这个样子直接操作，可能会让后面产生更多的0呀！但这个样子想就错了，因为题目要求我们把整个字符串都变成1，而每次操作都只能对编号的倍数倍进行操作，换而言之，如果对编号 x 操作，那么显然操作不会对小于 x 的字符操作，而如果前面的0没有操作，你们后面的操作就无法让前面的0变为1。

因此，我们在遇见0必需操作，否则我们无法把整个字符串都变成1。

那么接下来就非常简单了，直接模拟即可。提供如下一份参考代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        char c;
        cin >> c;
        a[i] = int(c - '0');
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        if(!a[i]){
            ans++;
            for(int j = i; j <= n; j += i) a[j] ^= 1;   
        }
    }
    cout << ans;
    return 0;
}

最后感谢各位观看！