Strange Fractions（奇怪的分数）-数论

Strange Fractions[2021 ICPC 上海站 D]&U207965 Strange Fractions 增强版
参考（全题解）
题目链接中，增强版 T 增加到了 1e6，并要求 a,b 互质，ban掉了第一种做法（赛版不要求 a,b 互质）；

题目大意

给定一个正分数 $\frac pq$，我们需要找到两个正整数 $a,b$ 满足 $\frac pq=\frac ab+\frac ba$ ，如果不存在，则输出 $0,0$ ；
（ $1≤T≤10^5,1≤p,q≤10^7$ ，要求 $1≤a,b≤10^9$ ）

试差

思路

在 p,q 化为最简后，等价于寻找 a,b 满足 $\frac{a^2+b^2}{ab}=\frac pq$ ，我们只需要预处理出所有小于 1e7 的平方数，依次匹配~
时间复杂度 $O(T\sqrt p)$ ；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int twi[10004];
int tti[10000007];
int main()
{
    int t,p,q;
    for(int i=1;i*i<=10000000;i++)
    {
        twi[i]=i*i;
        tti[i*i]=i;
    }
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&p,&q);
        if (p < 2 * q) {
            printf("0 0\n");
            continue;
        }
        int g=__gcd(p,q);
        p/=g,q/=g;
        int f=0;
        for(int i=1;twi[i]<=p&&!f;i++)
        {
            int lst=tti[p-twi[i]];
            if(lst&&i*lst==q)
            {
                printf("%d %d\n",min(i,lst),max(i,lst));
                f=1;
            }
        }
        if(!f)printf("0 0\n");
    }
}

二进制枚举

思路

我们可以证明 a,b 互质时 $gcd(a^2+b^2,ab)=1$ 成立， $\frac pq$化简后，我们便可以处理出 p 的所有互质因子对 a,b ，并验证与 q 的关系;
至于为什么要求是互质因子对，可以简化枚举过程和省略枚举后的约分，由于质因子最多8个（$2\cdot3\cdot5\cdot 7\cdots19$），所以时间复杂度 $O(T2^8)$ ；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e7;
int pri[N + 7], c = 0, mrk[N + 7];
bool n[N + 7];
void prime()
{
    n[0] = n[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!n[i])
            pri[c++] = i, mrk[i] = i;
        for (int j = 0; j < c && i * pri[j] <= N; j++)
        {
            n[i * pri[j]] = 1;
            mrk[pri[j] * i] = pri[j];
            if (i % pri[j] == 0)
            {
                mrk[pri[j] * i] *= mrk[i];
                break;
            }
        }
    }
}
int v[10];
void solve()
{
    int tot = 0, f = 0, a, b, p, q;
    scanf("%d%d", &p, &q);
    if (p < 2 * q)
    {
        printf("0 0\n");
        return;
    }
    int g = __gcd(p, q);
    p /= g, q /= g;
    tot = 0, f = 0;
    while (q != 1)
    {
        v[tot++] = mrk[q];
        q /= mrk[q];
    }
    for (int i = 0; i < (1 << tot); i++)
    {
        a = 1, b = 1;
        for (int j = 0; j < tot; j++)
        {
            if ((i >> j) & 1)
                a *= v[j];
            else
                b *= v[j];
        }
        if (a * a + b * b == p)
        {
            printf("%d %d\n", min(a, b), max(a, b));
            return;
        }
    }
    printf("0 0\n");
    return;
}
int main()
{
    int t;
    prime();
    cin >> t;
    while (t--)
    {
        solve();
    }
}

求根公式

思路

不妨设 $\frac ab=x$ ，那么有 $\frac pq=x+\frac1x$ ，问题转化为求 $qx^2-px+q=0$ 的有理根；
由于求根公式 $x=\frac{p+\sqrt{p^2-4q^2}}{2q}$ ，在判断根式有理后，即可获得分子分母；
时间复杂度 $O(T\log p)$ ；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll t,p,q;
    cin>>t;
    while(t--)
    {
        scanf("%lld%lld",&p,&q);
        if (p < 2 * q) {
            printf("0 0\n");
            continue;
        }
        ll g=__gcd(p,q);
        p/=g,q/=g;
        ll s=(ll)sqrt(p*p-4*q*q);
        if(s>=0&&s*s==p*p-4*q*q)
        {
            ll fz=p+s,fm=2*q;
            ll gtmp=__gcd(fz,fm);
            fz/=gtmp,fm/=gtmp;
            printf("%lld %lld\n",min(fz,fm),max(fz,fm));
        }
        else printf("0 0\n");
    }
}

ED

\