目录
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
二、解题报告
1、思路分析
2、复杂度
3、代码详解
一、题目
1、题目描述
2、输入输出
2.1输入
2.2输出
3、原题链接
B - Chladni Figure
二、解题报告
1、思路分析
给定 k，如何 check k是否是合法解？
只要每个线段旋转后，在其旋转后的位置仍然有线段存在即可，因为n条线段旋转同样的角度后不重合，所以正确。检查一次为O(M)
对于合法的k，如果k合法，那么2k也合法，3k也合法……
即kx % n 合法
有裴蜀定理可得 ax + bn = gcd(x, n)
那么 k 显然是 n 的因子的倍数，因子数量级是O(log)的，但是我们无法直接得到因子，试除法又太慢了，如何操作？
我们考虑枚举质因子p，然后检查n / p是否合法，由于 n / p一定是n 某个因子的倍数，我们处理所有质因子是很快的，且对于k合法，k的倍数也合法，所以保证了n的每个因子一定能被check或者其倍数一定被check
2、复杂度
时间复杂度： O(mlogn)空间复杂度：O(n)
3、代码详解
#include <bits/stdc++.h>using i64 = long long;
using i32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;constexpr int inf32 = 1E9 + 7;
constexpr i64 inf64 = 1E18 + 7;
constexpr int P = 998'244'353;/*旋转 k 可行，则旋转 kx 也可行旋转 kx mod n 也可行ax + bn = gcd(x ,n)
*/void solve() {int n, m;std::cin >> n >> m;std::set<std::pair<int, int>> st;std::vector<std::pair<int, int>> segs(m);for (int i = 0, a, b; i < m; ++ i) {std::cin >> a >> b;-- a, -- b;if (a > b) std::swap(a, b);st.emplace(a, b);segs[i] = { a, b };}for (int i = 2, t = n; i <= n && t > 1; ++ i) {if (t % i == 0) {while (t % i == 0) t /= i;int x = n / i;bool ok = true;for (int j = 0; j < m; ++ j) {auto [l, r] = segs[j];int nl = (l + x) % n, nr = (r + x) % n;if (nl > nr) std::swap(nl, nr);if (!st.contains(std::pair(nl, nr))) {ok = false;break;}}if (ok) {std::cout << "Yes";return;}}}std::cout << "No";
}auto FIO = []{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);return 0;
}();int main () {#ifdef DEBUGfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endifint T = 1;// std::cin >> T;while (T --) {solve();}return 0;
}