Sun and Moon (AOJ2455)

問題文が読めない人のために問題文を書くと,
N(<=1000)人います.人はグループAかBのどちらか一方です.各人にはo[i]とp[i]が定められています. 0<=o[i]<=1e9,1<=p[i]<=1e15です.ただしグループBのひとはp[i]の符号が負で渡されます.
Σ(グループAに属している人)o[i]*p[i]*x^(o[i]-1) = Σ(グループBに属している人) 左同
かつ
Σ(グループAに属している人)p[i]*x^o[i] = Σ(グループBに属している人) 左同
をみたすような最小の正整数xを返してください.

地頭1,ライブラリ0,実装1,英語(というかエスパー力)5 という感じ

まず問題文が論外なのは置いておきます.
とりあえず上式を移行すると問題文で与えられてる通りの符号のままでΣ(0<=i<N)o[i]*p[i]*x^(o[i]-1) =0 となる(下も同様)ことがわかる.
上の式は下の式(fとおく)をxで微分したものなので,それが両方aで0になるというのはfが(x-a)^2で割り切れるのと同値.なのでfの次数が最も小さい項の係数(の絶対値)をcとすると,cはa^2の倍数.cは1e15*1000 くらいになるので,約数列挙はヤバイ.よく考えるとa^2で割れるようなaしか必要ないので,10^6までの素数で割っておくと,あとはたかだか素因数は二つなので,その二つが同じ数でないかぎりaの素因数として出てこないことがわかる.なので平方数かどうか判定するだけでOK.あとは列挙して,それぞれに対し上の2つの式が0になるかどうか確かめればいい(次数が小さい項からうまく足していっても判定できるけど面倒なので適当なmodをとった,1145141919対策されてないので安心して使ってください.)
マジで問題文ふざけんなよ・・・
はてな記法で小なりが変になってた

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N;
typedef long long ll;
map<ll,ll> f,f_;
const int T=1;
ll mod=1145141919;
ll ex(ll x,ll p){
	ll a=1;
	if(p<0) return 0;
	while(p){
		if(p%2) a=a*x%mod;
		x=x*x%mod;
		p/=2;
	}
	return a;
}
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}

const ll ccc=1000000;
bool prime[ccc+1];
vector<ll> pr;
void makeprime(){
	ll i,j;
	for(i=2;i<=ccc;i++) prime[i]=true;
	for(i=2;i*i<=ccc;i++) if(prime[i]) for(j=2;j*i<=ccc;j++) prime[j*i]=false;
	for(i=2;i<=ccc;i++) if(prime[i]) pr.push_back(i);
}

map<ll,int> fac;
vector<ll> ds;
void dfs(map<ll,int>::iterator it,ll d){
	if(it==fac.end()){
		ds.pb(d);
		return;
	}
	ll p=it->fs,q=it->sc,t=1;
	auto it2=it;
	it2++;
	rep(i,q/2+1){
		dfs(it2,d*t);
		t*=p;
	}
}
int main(){
	makeprime();
	cin>>N;
	rep(i,N){
		ll a,b;
		cin>>a>>b;
		f_[a]+=b;
	}
	for(auto p:f_) if(p.sc!=0) f[p.fs]=p.sc;
	if(f.empty()){
		puts("Yes 1");
		return 0;
	}
	ll c=abs(f.begin()->sc);
//	show(c);
	ll tmp=c;
	for(ll p:pr){
		while(tmp%p==0) tmp/=p,fac[p]++;
	}
	if(tmp>1){
		ll a=round(sqrt(tmp));
		if(a*a==tmp) fac[a]=2;
	}
	dfs(fac.begin(),1);
	sort(all(ds));
	for(ll a:ds){
		bool ok=1;
		ll x=0;
		for(auto p:f) add(x,p.sc%mod*ex(a,p.fs));
		if(x!=0) ok=0;
		x=0;
		for(auto p:f) add(x,-p.sc%mod*p.fs%mod*ex(a,p.fs-1));
		if(x!=0) ok=0;
		if(ok){
			cout<<"Yes "<<a<<endl;
			return 0;
		}
	}
	puts("No");
}