题解：P17348 [ECNA 2025] How Many Balls?

· · 题解

思路

由于 r \le 1 \times 10^6，考虑枚举 r，O(1) 计算 g 然后检查。

因为

\frac {2rg}{(r+g)(r+g−1)} = \frac {p}{q}

所以

2qrg = p(r+g)(r+g−1)

拆开得

2qrg = pr^2 + pg^2 + 2prg - pr - pg

整理得

pg^2 + (2pr - 2qr - p)g + pr^2 - pr = 0

我们知道，对于方程

ax^2 + bx + c = 0

令

\Delta = b^2 - 4ac

则

x = \frac {-b \pm \sqrt {\Delta}}{2a}

将 a = p ,b = 2pr - 2qr - p,c = pr^2 - pr 代入方程计算并检验即可。

复杂度分析

时间复杂度为 O(R)，其中 R = 1 \times 10^6。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int R=1000000;
int a,b,c,p,q;
void Get(int &ans1,int &ans2)
{
    int D=b*b-4*a*c;
    ans1=ans2=-1;
    if(D<0) return;
    int Sq=(int)sqrt(D);
    if(Sq*Sq!=D) return;
    if((-b-Sq)%(2*a)==0) ans1=(-b-Sq)/(2*a);
    if((-b+Sq)%(2*a)==0) ans2=(-b+Sq)/(2*a);
}
bool check(int r,int g)
{
    if(g<r) return 0;
    return 2*q*r*g==p*(r+g)*(r+g-1);
}
signed main()
{
    cin>>p>>q;
    for(int r=1,g1,g2;r<=R;r++)
    {
        a=p,b=2*p*r-2*q*r-p,c=p*r*r-p*r;
        Get(g1,g2);
        if(check(r,g1))
        {
            cout<<r<<' '<<g1;
            return 0;
        }
        if(check(r,g2))
        {
            cout<<r<<' '<<g2;
            return 0;
        }
    }
    cout<<"impossible";
}