题解：AT_abc480_e [ABC480E] Product-Bounded Arithmetic Sequences

· · 题解

被 C 硬控 30 分钟的我愤怒了，直接 3 分钟写完 D、4 分钟写完 E。

想要确定一个等差数列，只需要确定以下三个量即可：

  1. 首项。
  2. 公差。
  3. 项数。

由于项数至少为 3，而积最多为 10^{18}，故首项最大为 ^3\sqrt{10^{18}}=10^6。而我们注意到项数也是很少的，只有 \log 级别，因此我们可以枚举首项和项数。

在确定首项和项数后，我们发现合法答案的公差是具有单调性的，所以可以二分确定公差。而计算一个等差数列的积就直接暴力计算即可。

理论时间复杂度为 O(^3\sqrt n\log^3n)，但常数极小，并且可以加一大堆剪枝，能直接冲过 AT 神机。

:::success[AC code]

#include<bits/stdc++.h>
#define int __int128
using namespace std;
long long n,ans;
inline bool check(int st,int x,int len)
{
    int s=1;
    for(int i=st,j=1;j<=len;i+=x,j++)
    {
        s*=i;
        if(s>n)return 0;
    }
    return 1;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=1000000;i++)//枚举首项
        for(int j=3,s=i*(i+1)*(i+2);s<=n;s*=i+j,j++)//枚举项数
        {
            int l=1,r=1000000000,mid=0,ss=0;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(check(i,mid,j))ss=mid,l=mid+1;
                else r=mid-1;
            }//二分公差
            ans+=ss;
        }
    cout<<ans;
    return 0;
}

:::