phpcms 做好网站怎么保存,免费域名怎么做网站,平面设计和网站建设哪个好,微信网站建设所谓整除分块#xff0c;就是按照整除的结果分块 #xff08;逃#xff09;
解析
一个关键的结论#xff1a; 对于 i≤ni\le ni≤n#xff0c;满足 ⌊nx⌋⌊ni⌋\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{n}{i}\rfloor⌊xn⌋⌊in⌋ 的最大的 xxx 为 ⌊n⌊ni⌋⌋\lfl… 所谓整除分块就是按照整除的结果分块 逃
解析
一个关键的结论 对于 i≤ni\le ni≤n满足 ⌊nx⌋⌊ni⌋\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{n}{i}\rfloor⌊xn⌋⌊in⌋ 的最大的 xxx 为 ⌊n⌊ni⌋⌋\lfloor\dfrac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor⌊⌊in⌋n⌋。 证明 设 k⌊ni⌋k\lfloor\dfrac{n}{i}\rfloork⌊in⌋那么就有 ni⋅kp(0≤pi,pnmodi)ni\cdot kp\pod{0\le pi,pn\bmod i}ni⋅kp(0≤pi,pnmodi)设 xidxidxid同理有 n(id)⋅kp′(0≤p′x,p′nmodx)n(id)\cdot kp\pod{0\le px,pn\bmod x}n(id)⋅kp′(0≤p′x,p′nmodx)化简得 p′p−dkpp-dkp′p−dk由于 p′0p0p′0有 d⌊pk⌋d\lfloor\dfrac{p}{k}\rfloord⌊kp⌋。 那么就有 xmaxidmaxx_{max}id_{max}xmaxidmax i⌊pk⌋i\lfloor\frac{p}{k}\rfloori⌊kp⌋ i⌊nmodik⌋i\lfloor\frac{n\bmod i}{k}\rfloori⌊knmodi⌋ ⌊in−⌊ni⌋⋅i⌊ni⌋⌋\lfloor i\frac{n-\lfloor \dfrac{n}{i}\rfloor\cdot i}{\lfloor\dfrac{n}{i}\rfloor}\rfloor⌊i⌊in⌋n−⌊in⌋⋅i⌋ ⌊n⌊ni⌋⌋\lfloor \frac{n}{\lfloor\dfrac{n}{i}\rfloor}\rfloor⌊⌊in⌋n⌋ 证毕。
代码
(计算因数个数的前缀和
ll calc(ll x){if(x0) return 0ll ans0;for(ll l1,r;lx;lr1){rx/(x/l);(ans1ll*(r-l1)*(x/l))%mod;}return ans;
}
