Skip to content

Instantly share code, notes, and snippets.

@asi1024
Last active August 27, 2015 21:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save asi1024/2313bed870e862c667e9 to your computer and use it in GitHub Desktop.
Save asi1024/2313bed870e862c667e9 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, pi = acos(-1.0);
const int mod = 1000000007;
struct Mod {
int num;
Mod () : num(0) {;}
Mod (ll n) : num((n % mod + mod) % mod) {;}
};
Mod operator+(Mod a, Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator*(Mod a, Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator+=(Mod &a, Mod b) { return a = a + b; }
Mod operator^(Mod a, ll n) {
if (n == 0) return Mod(1);
Mod res = (a * a) ^ (n / 2);
if (n % 2) res = res * a;
return res;
}
map<ll,ll> expr;
bool judge(int i) {
Mod sum1 = 0, sum2 = 0;
for (auto p: expr) sum1 += Mod(p.first) * Mod(p.second) * (Mod(i) ^ (p.first-1));
for (auto p: expr) sum2 += Mod(p.second) * (Mod(i) ^ p.first);
return sum1.num == 0 && sum2.num == 0;
}
ll solve() {
int n; cin >> n;
REP(i,n) {
ll o, p; cin >> o >> p;
expr[o] += p;
}
auto it = expr.begin();
while (it != expr.end() && (it->second == 0 || it->first == 0)) ++it;
if (it == expr.end()) return 1;
ll num = abs(it->second), res = -1;
for (ll i = 1; i * i <= num; ++i) {
if (num % i > 0) continue;
if (judge(i)) return i;
if (judge(num/i)) res = num/i;
}
return res;
}
int main() {
ll res = solve();
if (res == -1) cout << "No" << endl;
else cout << "Yes " << res << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment