在想只有一个数的时候混乱了，先思考再开码很重要。
https://codeforces.com/contest/1594/problem/C
题意
给定一个字符串和目标字符 \(c\)，每次操作可以选中一个 \(i\)，并将所有 \(j,\ j\mod i \not= 0\) 位置处的字符变为\(c\)，问最少多少次操作可以将整个字符串上的每个数都变成目标字符。
Turotial
首先容易发现第一次选 \(n\)， 第二次选 \(n-1\) 一定可以将整个串变成目标串。
接下来只需要考虑能不能选择一个数就将串变成目标串。自然想到可以枚举 \(i,\ i \in [2,n]\)，对于每个 \(i\) 检查是否存在 \(a_j \not = c,\ j \equiv 0 \mod i\)，如果存在，则说明选当前的 \(i\) 时 \(a_j\) 不会被消除，那么当前 \(i\) 是无效的。直接枚举 \(i\) 的倍数处字符，复杂度为调和级数 \(O(n\log n)\).
点击查看代码
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <vector>
typedef long long ll;
#define endl '\n'
#define P pair<int, int>
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
// int visit[N];
bool isprime[N], vis[N];
int prime[N];
string s;
void Prime() {
memset(isprime, true, sizeof isprime);
isprime[0] = isprime[1] = false;
for (int i = 2; i <= N; i++) {
if (!isprime[i]) continue;
prime[++prime[0]] = i;
for (int j = 2; i * j <= N; j++) {
isprime[i * j] = false;
}
}
}
void divide(int x) {
for (int i = 1; i <= prime[0] && prime[i] * prime[i] <= x; i++) {
if (x % prime[i] == 0) vis[prime[i]] = 1;
while (x % prime[i] == 0) {
x /= prime[i];
}
}
if (x >= 1) vis[x] = 1;
}
int num[N], tot;
int main() {
IOS
int T;
cin >> T;
int n;
char to;
while (T--) {
tot = 0;
cin >> n >> to >> s;
for (int i = 0; i < n; i++)
if (s[i] != to) tot++;
if (tot == 0) {
cout << 0 << endl;
} else if (tot == 1) {
cout << 1 << endl;
if (s[n - 2] == to)
cout << n - 1 << endl;
else
cout << n << endl;
} else {
bool f = 0;
s = "-" + s;
for (int i = 1; i <= n; i++) {
bool ff = 1;
for (int j = i; j <= n; j += i) {
if (s[j] != to) {
ff = 0;
break;
}
}
if (ff) {
cout << 1 << endl << i << endl;
f = 1;
break;
}
}
if (f) continue;
cout << 2 << endl << n - 1 << " " << n << endl;
}
}
}