poj 2645 - Boastin 'Red Socks - 컴 포 지 팅.

제목: p 와 q 를 드 리 겠 습 니 다. 검 은 상자 에서 한 번 에 양말 두 개 를 가 져 오 는 것 을 의미 합 니 다. 두 개 모두 빨 간 양말 일 확률 은 p / q 입 니 다.상자 안에 빨 간 양말 이랑 검 은 양말 이 얼마나 들 어 있 냐 고요?
해석:
우선 p / q 가 어떻게 왔 는 지 명 확 히 하 세 요.우 리 는 전체 양말 의 수량 이 i 이 고 빨 간 양말 의 수량 은 j 라 고 가정 한다.
p / q 는 C (j, 2) / C (i, 2) 입 니 다.즉 j (j - 1) / (i * (i - 1) = p / q;
이때 i 를 매 거 하여 j 의 값 을 계산 합 니 다.
주의: i * (i - 1) = tmp 가 i 를 요구 하면 i = (int) sqrt (tmp + 0.5) + 1 입 니 다.
자세 한 코드 분석:
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring> 
#include<cmath>
#include<queue>
using namespace std;
#define sf scanf
#define pf printf
#define INF 1<<29
#define eps 1e-6
const double PI=acos(-1.0);
#define lint __int64
#define LL long long 
#define ULLint unsigned long long //2^64-1>1.8*10^19
#define clr(x) memset(x,0,sizeof(x))
#define Clr(x) memset(x,-1,sizeof(x))
LL gcd(LL a , LL b){ 
	return b==0 ? a : gcd(b,a%b);
}
int main(){
	LL p,q;
	while(sf("%lld%lld",&p,&q)){
		if(!p && !q) break;
		if(p==q){
			pf("2 0
"); continue; } if(p==0){ printf("0 2
"); continue; } LL g=gcd(p,q); p/=g; q/=g; LL i,j; for(i=2; i<=50000; i++) if(i*(i-1)%q==0){ LL n=i*(i-1)/q; LL m=n*p; j=(LL)sqrt(m+0.5)+1; if(j*(j-1)==m && j>=2) break; } if(i>50000) pf("impossible
"); else pf("%lld %lld
",j,i-j); } return 0; }

좋은 웹페이지 즐겨찾기