题解 CF822D 【My pretty girl Noora】
素质玩家孙1超
·
·
题解
来一发全场最慢解，总共跑了 \rm 1.16 \min ,但是思路简单，代码好写。
用 n\log n 大力跑过 5 \times 10^6，本题时限 \rm 1.5 \ s 我最慢的一个点跑了 \rm 1497 \ ms。
题意：
+ 设当前人数为 $m$ ，选择一个正整数 $x(m≥x>1,x ∣ m)$ ，划分为 $\frac{m}{x}$ 组，每组 $x$ 个人。
+ 每一组中的女生两两比较，共进行 $\frac{x\times(x-1)}{2} $ 次比较。最终每一组只会有 $1$ 名女生晋级。
+ 所有晋级的女生继续进行选美，直到只剩下一名女生。
设初始为 $n$ 名女生时最少的总比较次数为 $f(n)$，求
$$\sum_{i=l}^r t^{i-l}\times f(i) \mod (10^9+7)$$
---
其实就是批量求一个 $f(i)$ 然后最后用一种奇怪的方式求和之后输出。
开始，我们可以有一个幼稚的想法，直接枚举因数取 $\min$ 。式子是这个：
$$f(i) = \min _{d|n} \frac{n}{d}\times \frac{d(n-1)}{2} \times f(\frac{n}{d})$$
其实 $\sum_{i=1}^n \sum_{d|i} 1$ 是 $O(n \log n )$ 的，但我们直接枚举因数是 $O(n\sqrt n)$ 的，考虑如何优化这个东西。
我们枚举复杂度不够优的原因是枚举了大量不是因数的东西，所以我们把式子搞成递推的形式，就可以直接枚举倍数而不多枚举了。这个是递推式：
$$f(i\times j)=\min (f(i \times j),f[i]+ \frac{j\times i \times (j-1)}{2})$$
其实这个转换挺常见的，然后枚举代码变成
```cpp
for(int i=1;i<=n;i++)
for(int j=2;j*i<=n;j++)
```
就是 $O(n\log n )$ 的了，就可以（靠着cf的评测机）大力艹过去了。
（这个 $O(n\log n )$ 有两种方式理解，一种是考虑意义是这个$\sum_{i=1}^n \sum_{d|i} 1$ ，还有一种是直接写式子发现是个调和级数求和就可以推出来了）
---
代码：
```cpp
#include<bits/stdc++.h>
inline int R()
{
char c;int sign=1,res=0;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;res+=c-'0';
while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
return res*sign;
}
using namespace std;
#define int long long
const int Maxm=5e6+5;
const int Mo=1e9+7;
int n,m,f[Maxm],t,l,r;
signed main()
{
memset(f,0x7f,sizeof f);
t=R();l=R();r=R();n=r;
f[1]=0;
for(int i=1;i<=n;i++)
for(int j=2;j*i<=n;j++)
f[i*j]=min(f[i*j],f[i]+1ll*j*i*(j-1)/2);
int ans=0,S=1;
for(int i=l;i<=r;i++)
{
ans=(ans+S*(f[i]%Mo))%Mo;
S=S*t%Mo;
}
printf("%lld\n",ans);
}
```