给定$(a_i,b_i)~i\in[1,k]$, 找到所有n满足$a_i\equiv b_i~~(mod~~n)$.

令$x_i=|a_i-b_i|$, 有$n|x_i$, 所以有$n|gcd(X)$, 其中$X=\{x_1,x_2,...,x_k\}$. 求得最大公约数后再分解因子, $\Theta(klogw\sqrt w)$.

#include <bits/stdc++.h>
using namespace std;

set<int> sep(int x)
{
	set<int> s;
	for (int i = 1; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			s.insert(i);
			s.insert(x / i);
		}
	}
	return s;
}

void solve()
{
	int k; cin >> k;
	int x, y; cin >> x >> y;
	int g = __gcd(x, y);
	while (--k)
	{
		cin >> x >> y;
		g = __gcd(g, x);
		g = __gcd(g, y);
	}
	set<int> s = sep(g);
	for (int x : s) cout << x << " ";
	cout << "\n";
}

int main()
{
	int T = 1; // cin >> T;
	while (T--) solve();	
	return 0;
}