E题: Math

原题链接:https://ac.nowcoder.com/acm/contest/11254/E

题目大意

给定 n ( 1 ≤ n ≤ 1 0 18 ) n(1\le n\le 10^{18}) n(1≤n≤1018) ，求满足 x y + 1 ∣ x 2 + y 2 xy+1|x^2+y^2 xy+1∣x2+y2 的正整数对 ( x , y ) ( 1 ≤ x ≤ y ≤ n ) (x,y)(1\le x\le y\le n) (x,y)(1≤x≤y≤n) 的数量。

题解

通过打表查找小范围内的数对，我们不难发现以下两条规律:
①:若不存在小于 x x x 的 y y y 可与 x x x 配对，则与 x x x 可配对的最小 y y y 是 x 3 x^3 x3 ，例如:
2—8
3—27
4—64
②:对于非 ( x , x 3 ) (x,x^3) (x,x3) 形式的数对，其呈现多组的 x x x 与 y y y 首位相同连成序列的形式，且首位呈 3 3 3 次幂的形式，例如:
8( 2 3 2^3 23 )—30—112—418—1560—5822—…
27( 3 3 3^3 33 )—240—2133—…
64( 4 3 4^3 43 )—1020—…
显然同时考虑两者，我们可以发现对于一条序列(将满足①的数对接到②的序列前方，如2—8—30—112—418—1560—5822—…)，其前两项必然为 ( x , x 3 ) (x,x^3) (x,x3) ，对于第二项开始，每一项 x x x 都有 2 2 2 个可以搭配组成合法数对的 y y y (一大一小，可以通过解关于 y y y 的一元二次方程 y 2 − k x y + x 2 − k = 0 y^2-kxy+x^2-k=0 y2−kxy+x2−k=0 证明有 2 2 2 个不同的解)。
对于为何前两项必然为 ( x , x 3 ) (x,x^3) (x,x3) 的形式和为何对于首位 x x x 为何仅有 x 3 x^3 x3 一个合法解，在此不给出 (给不出) 具体证明(属于是只会通过打表找规律的蒟蒻)。
对于编写代码解题而言，我们只需要对于每一个自然数找出其往后延伸的序列，然后将序列内每相邻 2 2 2 个数组成的合法数对存储下来即可。
对于式子 x y + 1 ∣ x 2 + y 2 xy+1|x^2+y^2 xy+1∣x2+y2 ，我们将其写为 k ( x y + 1 ) = x 2 + y 2 k(xy+1)=x^2+y^2 k(xy+1)=x2+y2 的形式。
若我们知道 x x x 与 k k k 的值，上式可化简为关于 y y y 的一元二次方程 y 2 − k x y + x 2 − k = 0 y^2-kxy+x^2-k=0 y2−kxy+x2−k=0 ，由韦达定理易得 k x = y 1 + y 2 kx=y_1+y_2 kx=y1​+y2​ ，改写作 y 2 = k x − y 1 y_2=kx-y_1 y2​=kx−y1​ 的形式，我们就得到了关于一条序列的一般递推式(对于我们当前处理的序列，我们已知前两项 ( x , x 3 ) (x,x^3) (x,x3) ，那么我们就可以代入算得 k = x 2 k=x^2 k=x2 ，并利用 x = x , y = x 3 x=x,y=x^3 x=x,y=x3 这组合法解开始递推)。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN=1e18+5;
int t;
ll n,ans[2000005],cnt;
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0);
    ll i,j,x,y,k,p;
    ans[cnt++]=1;//第一条序列为1—1—1—1—1—1—1—1—...,特判提前放入
    for(i=2;i<=1000000;i++){
        x=i,y=x*x*x,k=y/x;//对于每个数初始计算好k与第一组(x,y)
        ans[cnt++]=y;//存储时放入数对中的较大值,方便二分查找
        while(y<=(MAXN+x)/k){//控制递推,超过数据范围即不存在下一组解
            p=y;
            y=k*y-x;//计算新的y2，因为此时(x,y)的大小关系翻转,所以要换位
            x=p;//将原来的y的值赋给x
            ans[cnt++]=y;//存储时放入数对中的较大值，方便二分查找
        }
    }
    sort(ans,ans+cnt);
    cin>>t;
    while(t--){
        cin>>n;
        printf("%d\n",upper_bound(ans,ans+cnt,n)-ans);//二分查找第一个超过n范围的非法数对，取得下标即是合法数对数量
    }
    return 0;
}