CodeForces#557 Div2D Chladni Figure

Problem - D - Codeforces

概要

円周上に等間隔でn個の点があり、いくつかの点同士が線で結ばれており、その辺の数はm本である。
この図形が回転対称(rotationally symmetrical)であるかどうかを判定せよ。

制約

2 ≦ n ≦ 100 000
1 ≦ m ≦ 200 000

方針

回転対称のナイーブな判定方法としては、1 ≦ k ≦ n - 1なる整数kについて、辺で結ばれた関係をそのままにk個右に頂点を回転させたとき、
元の図形に一致するkが存在すればその図形は回転対称である。

元の図形に一致するかどうかは元の図形の辺を要素2個のタプルのセットにいれ（タプルは昇順にする）、移動させた各辺がセットにすべて含まれるかを判定すればよい。ただこの判定はO(NMlogM)かかってしまう。

実は元の図形に一致するkはnの約数を調べるだけでよいらしく、
約数の個数のオーダーが分かりませんが、問題を解くために十分小さな量になるようです。
何故約数だけでよいのか要確認です。（ここが最も重要…）

解答

https://codeforces.com/contest/1162/submission/53889263

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

pii make_sorted_pair(int i, int j){
	return (pii){min(i, j), max(i, j)};
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	set<pii> st;
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		st.insert(make_sorted_pair(a - 1, b - 1));
	}

	for(int k = 1; k < n; k++){
		if(n % k != 0) continue;

		bool ok = true;
		for(pii p : st){
			if(st.count(make_sorted_pair((p.first + k) % n, (p.second + k) % n)) == 0){
				ok = false;
				break;
			}
		}

		if(ok){
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}