Day2 T4 数论函数
也是非常巧妙地一道题，思引在于多项式取模。
首先，对于限制 \(b+i\mid a+w\times i^2\)，将其看作关于 \(i\) 的多项式，则有 \((a+w\times i^2)\equiv 0 \mod\ (b+i)\)，进行大除法（或者多项式取模），将原式化简可以得到 \(b+i\mid a+w\times b^2\)。
于是若 \(f(a,b)=k\) 则有 \(lcm(b+i[i\le k])\mid a+w\times b^2\)。
考虑计算贡献 \(f(a,b)=k\) 拆分为 \(\sum_k f(a,b)\ge k\)，则对于每一个 \(k\) 我们单独讨论。
当 \(k=0\) 时，没有意义。
当 \(k>1\) 时，有 \(lcm\ge \dfrac{b\times (b+1)\times (b+2)}{2}\)，当 \(O(b^3-w\times b^2)> n\) 时，对于所有 \(a\) 都有 \(f(a,b)=0\)，当 \(n=10^{18}\) 时候，\(b\) 取到 \(3\times 10^6\) 即可，贡献的计算显然。
当 \(k=1\) 时，则有：
\[a+w\times b^2\equiv 0 \mod\ b\times(b+1) \]因为有 \(b(b+1)\equiv 0\)，所以 \(b^2\equiv -b\)，于是原式转化为：
\[a\equiv w\times b\mod\ b\times (b+1) \]显然，我们可以枚举每个 \(b\) 来计算，答案为 \(\lfloor\dfrac{n-min_a}{b\times (b+1)}\rfloor+1\)，但这样是不优的。
观察到 \(w\) 是个定值，那么如果 \(a\) 的最小取值就恰好等于 \(w\times b\)，我们貌似可以用某种方式来优化它。
那么什么时候 \(min_a=w\times b\) 呢，当且仅当 \(w<b+1\) 即 \(w\le b\) 时。
所以分两类，对于 \(b<w\) 的，暴力枚举计算时间复杂度为 \(O(w)\)，对于大于的部分，考虑加速。
此时答案为：
\[\lfloor\frac{n-w\times b}{b\times (b+1)}\rfloor=\lfloor\frac{\lfloor\frac{n}{b}\rfloor-w}{b+1}\rfloor \]设这个它为函数 \(f(b)\)。
发现这个东西，当 \(b\ge \sqrt[3]{n}\) 的时候，\(\lfloor f(b)\rfloor\) 的取值只有 \(\sqrt[3]{n}\) 的级别。
所以这样就可以根号分治了，对于 \(b\le \sqrt[3]{n}\) 的部分暴算，对于大于的部分则考虑快速找出 \(f(b)=x\) 的所有 \(b\)。
假如 \(f(b)=x\) 的 \(b\) 都是一段连续的区间，那么对于 \(l\) 我们可以去二分出 \(r\)，以此达到快速计算的目的。
注意，我们此处只要求其连续即可，不需要单调也是可以二分的。
但实际上可以考虑证明其是单调的来证明其是连续的。
即证明
\[\lfloor\frac{\lfloor\frac{n}{b}\rfloor-w}{b+1}\rfloor \ge \lfloor\frac{\lfloor\frac{n}{b+1}\rfloor-w}{b+2}\rfloor \]这是显然的，因为 \(\lfloor\dfrac{n}{b}\rfloor-w\ge \lfloor\dfrac{n}{b+1}\rfloor-w\)，又有 \(\lfloor\dfrac{x}{b+1}\rfloor\ge\lfloor\dfrac{y}{b+2}\rfloor\)，因为 \(x\ge y\)，\(b+2\ge b+1\) 则有 \(x\times (b+2)\ge y\times (b+1)\)。
证毕。
最终的复杂度为 \(O(\sqrt[3]{n}\times \log_2n)\)，可以通过这道题。
但是这样就够了吗？
当然不是，既然正常的整除分块可以做到不带 \(\log_2\) 那么这里也能做到。
对于 \(l\) 找到下一个边界，即计算 \(r,f(r)=val+1\)，由此我们可以列出一系列不等式：
\[\lfloor\frac{\lfloor\frac{n}{r}\rfloor-w}{r+1}\rfloor=val-1\\ (r+1)\times (val-1)\le \lfloor\frac{n}{r}\rfloor-w<(r+1)\times val\\(r+1)\times (val-1)+w\le \lfloor\frac{n}{r}\rfloor<(r+1)\times val+w \]为了方便表示，记为
\[L\le \lfloor \frac{n}{r}\rfloor \le R \]由于我们要求解 \(min_r\) 即第一个满足要求的 \(r\)，则有 \((r+1)\times (val-1)+w\ge \lfloor \dfrac{n}{r}\rfloor\)，转化一下则为
\[r\times (r+1)\times (val-1)+w\times r\ge n\\r^2\times (val-1)+r\times (val-1+w)+(val-1)\ge n \]这实际上就是一个一元二次不等式，\(O(1)\) 解出 \(r\) 的最小值即可。
最终的时间复杂度为严谨的\(O(\sqrt[3]{n})\)。
代码
倍增版本，暂未优化。
#include<bits/stdc++.h>
using namespace std;
#define i128 __int128
#define LL long long
const long long inf=1e18;
LL n,m,w,B=5e6;
i128 ans;
void write(i128 x){
if(x==0){
putchar('0');return;
}
static char Oupt[100];
int Cnt=0;
while(x){
Oupt[++Cnt]=(x%10)+'0',x/=10;
}
while(Cnt){
putchar(Oupt[Cnt--]);
}
}
i128 gcd(i128 a,i128 b){
if(b==0)return a;return gcd(b,a%b);
}
int main(){
scanf("%lld%lld%lld",&n,&m,&w),B=min(B,m);
for(LL b=1;b<=B;b++){
i128 wb=(i128)w*b*b,Lm=b;
for(LL i=1;i;i++){
i128 d=gcd(Lm,b+i);
Lm=Lm/d*(b+i);
if(Lm>n+wb)break;
else{
i128 wap=0;
wap=Lm-wb%Lm;if(n>=wap)ans+=(n-wap)/Lm+1;
}
}
}
LL l=B+1,r=0;
while(l<=m){
if(n/l<w){break;}
LL val=((n/l)-w)/(l+1)+1;
r=l;
for(LL i=60;i>=0;i--){
LL nw=r+(1ll<<i);
if(n/nw>=w and ((n/nw)-w)/(nw+1)+1==val){
r=nw;
}
}
if(r>=m){
r=m;
}
ans+=(i128)(r-l+1)*val,l=r+1;
}
write(ans);
return 0;
}
/*
b+i|a+b*b*w
lcm|a+b*b*w
a=-b*b*b mod lcm
b(b+1)|a+b*b*w
b(b+1)|a+bw
b*b=-b mod b(b+1)
b(b+1)|a-bw
[([a/b]-w)/(b+1)]
a=wb mod b(b+1)
13495448248526902
13495448242367869
*/