2021牛客暑期多校训练营3 E.Math 解题报告（结论、打表）

所以为什么会在这里出现imo题
https://ac.nowcoder.com/acm/contest/11254/E

通过率非常高的一题，然而因为我太菜了，并没有过

这题我认为算是一个套路，实在无法理解可以暂时就留个印象，以后还遇到类似的可以对比着看。
这道题一拿到手应该大部分人和我一样想到打表。打出一部分表后，我们发现，任意数都符合条件。

接下来，我们设，则我们固定x，方程可整理为，我们固定x（也就是说我们等会选择枚举x），则，由韦达定理：
那么，接下来，我们固定k，我们要计算的是系数为k的(x,y)对数
由上面的韦达定理可知：若一对值满足条件，则，另一对符合条件的，系数为k的数对为
我们现在知道符合条件，那么，也就说明符合条件，那么，我们可以通过找出以y作为第一个元素的数对，也就是
我们已知符合条件，因此，，即我们得到的新的数对为
再回头看，我们打表找出了一个特例：
所以，我们带回去，过程就是：

(此时k=x^2)

……
无限套娃下去。（有点类似于gcd）
之后就是把打出来的第二元素放进数组里，排序然后二分就行了。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef __int128 ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=(ans*a)%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
vector<ll>da;

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //clock_t c1 = clock();
    //===========================================================
    da.push_back(1);
    for(ll i=2;i<=1e6;++i){
        ll x=i,y=i*i*i,k=i*i;
        while(y<=1e18){
            da.push_back(y);
            ll tmp=k*y-x;
            x=y;
            y=tmp;
        }
    }
    sort(da.begin(),da.end());
    int t;read(t);
    while(t--){
        ll n;read(n);
        int pos=upper_bound(da.begin(),da.end(),n)-da.begin();
        write(pos);putchar('\n');
    }
    //===========================================================
    //std::cerr << "Time:" << clock() - c1 << "ms" << std::endl;
    return 0;
}