PKU 2645-Boastin' Red Socks

問題概要

タンスの引き出しに2枚以上50000枚以下の赤か黒の靴下が含まれている．
その引き出しから2枚靴下を取りだした時，赤の靴下のみ確立がp/qの時，それぞれの色の靴下の枚数を求めよ．
複数パターンある場合は合計枚数が最小の物を求めよ．

解法

p=0のときは"0 2"と無条件で返す．何故か"1 1"では駄目だった．

赤の枚数をr,全体の枚数をaとすると
r(r-1)/a(a-1)=p/qなので
r(r-1)=a(a-1)*p/qとなり
r=√(a(a-1)*p/q+0.25) +0.5
となる．
よって，aを適当に定めるとrはO(1)で求まるので，今度はそのrがr(r-1)*q=a(a-1)*pを満たすかを計算する．
このとき多倍長整数などを使うと間に合わないのでハッシュで計算する．

後はaを2から50000まで試していく

実装(C++)

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
using namespace std;
typedef unsigned long long int lli;

const int MOD=100000009;
const double EPS=1e-5;
int main(){
	lli p,q;
	for(;cin>>p>>q;){
		if(q==0)break;
		if(p==0){
			//cout<<"0 2"<<endl;
			//continue;
		}
		lli gcd=__gcd(p,q);
		p/=gcd;q/=gcd;

		bool ans=false;

		for(int cnt=2;cnt<=50000;cnt++){
			double r=sqrt(p/(double)q*((double)cnt*(cnt-1))+.25)+.5;
			lli rr=r+EPS;
			if(((long long)rr*(rr-1)%MOD*q%MOD)%MOD==((long long)cnt*(cnt-1)%MOD*p%MOD)%MOD){
				cout<<rr<<" "<<cnt-rr<<endl;
				ans=true;
				break;
			}
		}
		if(!ans){
			cout<<"impossible"<<endl;
		}
	}
	return 0;
}