总结题意
显然可以转化为序列问题嘛。
给出序列 \(A\{a_i\}\)，你需要通过若干次操作使其归零。
操作：
选定 \(d | n\)、\(k\)、\(r\)，对于序列中所有满足 \(i \bmod d = r\) 的位置加上 \(k\)。
题解
很明显，加减相互抵消，对于所有 \(d\)、\(r\) 相同的位置可以视作一次操作。
如何表示一次操作呢？
如果你还记得生成函数这个高级东西的话，这就很容易了。
先把原序列函数化，记作：
\[A(x) = \sum_{i=0}^{n-1}a_ix^i
\]
那么修改的增量多项式即为：
\[kf(d,r,x)
\]
\[f(d,r,x) = x^r\frac{1 - x ^ n}{1 - x ^ d}
\]
注意这里大于 \(n\) 的项可以不管他。
那么，有解当且仅当
\[\sum kf(d,r,x) = A(x)
\]
有解。
丢番图方程的有解判断应用裴蜀定理，则有解条件：
\[\gcd\{f(d,r,x)\} | A(x)
\]
谈论到这，我们发现
\[\frac{f(d,r,x)}{x^r} = f(d,0,x) \Rightarrow f(d,0,x) | f(d,r,x)
\]
所以 \(f(d,r,x),r\not=0\) 是没有贡献的，不用考虑。
于是我们现在令
\[f(d,x) = \frac{1 - x ^ n}{1 - x ^ d}
\]
有解：
\[\gcd\{f(d,x)\} | A(x)
\]
现在这步不是拆 \(A\) 就是拆 \(f\)，但 \(A\) 不是构造的，是输入的，所以我们讨论 \(f\)。
这里因式分解一下：
- \(x^n - 1\) 在复数域上的因式分解
设其根为 \(re^{i\theta}\)，
\[re^{i\theta} = 1
\]
\[(re^{i\theta})^n = 1
\]
\[r^ne^{in\theta} = 1 \times e^{i0}
\]
故
\[r^n = 1,n\theta = 2 \pi k,k \in Z
\]
\[r = 1,\theta = \frac{2k\pi}{n}
\]
\[x = e^{i\frac{2k\pi}{n}} = \omega_n^{k}
\]
显然，上式得证。
\[f(d,x) = \frac{\prod_{i=0}^{n-1} (x - \omega_n^i)}{\prod_{i=0}^{d-1} (x - \omega_d^i)}
\]
\[= \frac{\prod_{i=0}^{n-1} (x - \omega_n^i)}{\prod_{i=0}^{d-1} (x - \omega_n^{\frac{ni}{d}})}
\]
\[= \prod_{i=0}^{n-1}[\frac{n}{d} \not| i](x - \omega_n^i)
\]
实际上，把 \(\frac{n}{d} \not| i\) 换个形式书写就是 \(gcd(i,n) = 1\)，所以：
\[\gcd\{f(d,x)\} = \prod_{i=0}^{n-1}[gcd(i,n) = 1](x - \omega_n^i)
\]
不太好做，容斥一下变成算补集，构造下补集：
\[\prod_{i=0}^{n-1}[gcd(i,n) = 1](x - \omega_n^i) = \frac{x^n - 1}{\prod_{i \in Primes,i | n}(x^{\frac{n}{i}} - 1)}
\]
然后：
\[\frac{x^n - 1}{\prod_{i \in Primes,i | n}(x^{\frac{n}{i}} - 1)} | A(x)
\]
\[x^n - 1 | A(x)\prod_{i \in Primes,i | n}(x^{\frac{n}{i}} - 1)
\]
暴力循环卷积一下，算出右边。
没了。
code
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100005], tmp[100005];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) // A(x)
{
char ch;
cin >> ch;
a[i] = ch - '0';
}
int nn = n;
for (int i = 2; i <= nn; ++i) //[(x^{n/p} - 1)]H(x)
{
if (nn % i == 0)
{
for(int j=0;j<n;j++)
{
tmp[(j + n/i) % n] = a[j] - a[(j + n/i) % n];
}
for(int j=0;j<n;j++)
{
a[j] = tmp[j];
}
while (nn % i == 0)
{
nn /= i;
}
}
}
for (int i = 0; i < n; ++i)
{
if (a[i] != 0)
{
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
return 0;
}