Last active
August 27, 2015 21:39
-
-
Save asi1024/2313bed870e862c667e9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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