CSP - J T2

youyew2007 · 2022-11-05 10:10:08 · 个人记录

拿到这道题的第一件事，我们发现这个式子可以进行一个变形，变为 e \times d = p \times q-p-q+2，p + q = n - e \times d + 2 = m，我们发现确定了 p 也就确定了 q，考虑暴力枚举 p ，但是 m 有 10 ^ {9} 肯定会超时，我们需要考虑优化。

这里我们需要有一个知识，当两个正数和一定时，他们的差越小，他们的积越大，所以 p 在 [1,\frac {m}{2}] 这个区间内时，p \times q 也就是 n 是单调递增的，所以我们考虑使用二分。

当然这里我们需要注意：n 的值并不在 p \in [1,m] 时单调，不能直接将 r 的值设为 m，许多人考场在此犯错而爆0零。我们只需要枚举的是 p 的值，所以我们只需要枚举从 1 到 \frac {m}{2} 而非从 1 到 m。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

long long k,e,d,m,n;//别忘了开long long

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> k;
    while(k--)
    {
        cin >> n >> e >> d;
        m = n - e * d + 2;
        int l = 1,r = m >> 1;//位运算会快一点
        bool flag = false;
        while(l <= r)//注意这里 l 可以等于 r
        {
            int mid = (l + r) >> 1;
            long long num = mid * (m - mid);//这里算的是n,要开long long
            if(num == n)//如果等于 n 直接输出
            {
                cout << mid << ' ' << m - mid << endl;
                flag = true;
                break;
            }
            if(num < n)l = mid + 1;//小了就往中间取
            else r = mid - 1;//大了往两边取
        }
        if(!flag)cout << "NO" << endl;
    }
}

当然，我们还可以考虑用数学方法，我们有 p + q = m,p \times q = n，变形：q \times (m - q) = n， q^2 - mq + n = 0 然后直接一元二次方程求解，应该没人不会吧。

注意：有两个点需要特判，一个是 \Delta 是不是整数，一个是 \Delta 是不是小于 0。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

typedef long long ll;

ll n,d,e;
int t;    

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n >> d >> e;
        ll m = n - e * d + 2,l = m * m - 4 * n;
        ll delta = sqrt(l);
        if(delta * delta != l)//如果乘起来不是 l 说明delta不是整数，直接输出NO
        {
            cout << "NO" << endl;
            continue;
        }
        else if(delta < 0)//方程无解
        {
            cout << "NO" << endl;
            continue;
        }
        else
        {
            ll p = (m - delta) >> 1,q = (m + delta) >> 1;//求两根，delta 大于 0 ，不用判断呼唤的问题。
            cout << p << ' ' << q << endl;
        }
      } 
    return 0;
}

对于要不要判断 delta + m 是不是偶数，这里给出证明：

展开，有n^2-2ned+4n+e^2d^2-4ed+4 - 4n = delta^2

将所有偶数删去，变为n^2 +e^2d^2，令其等于 k，当 k 为奇数时，当且仅当 n 为奇数且 ed 为偶数 或 n 为偶数且 e,d 均为奇数。

若 n 为奇数， m = n - ed + 2 为奇数（奇数 + 偶数 + 偶数），delta 为奇数，此时分子为偶数。

若 ed 为奇数， m = n - ed + 2 为奇数（偶数 + 奇数 + 偶数），delta 为奇数，此时分子为偶数。

同时，若 m 为奇数，则 delta = m^2 - 4n 为奇数，分子为偶数。

综上：分子恒为偶数。