题解 CF822D 【My pretty girl Noora】
囧仙
2020-05-14 20:26:44
## 题目大意
$n$个女生，进行若干论选美。选美的方式如下：
- 设当前人数为$m$，选择一个正整数$x(m\ge 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)$。
## 题解
根据最终需要我们计算的式子，显然需要求出$x\in [l,r]$时**所有**的$f(x)$。不过$f(x)$比较复杂，让我们先证明几个结论。
### $0.$简单的化简
设总共$m$人，$x$个人分为一组，则一共需要比较$\frac{m}{x}\times \frac{x\times (x-1)}{2}=\frac{m\times (x-1)}{2}$。
这步化简主要是为了方便下面的推算，并没有什么难度。
### $1.$每次分组的人数按照从小到大排列
假设目前有$m$轮。进行两次选美，分别是$a$个人一组、$b$个人一组。$(a\ge b>1)$
先$a$后$b$，总比较次数为：
$$\frac{m\times (a-1)}{2}+\frac{m\times (b-1)}{2\times a} \kern{50pt} \cdots \cdots (1) \kern{-50pt}$$
先$b$后$a$，总比较次数为：
$$\frac{m\times (b-1)}{2}+\frac{m\times (a-1)}{2\times b}\kern{50pt} \cdots \cdots (2) \kern{-50pt}$$
两式相减，得到：
$$\begin{aligned}(1)-(2)&=\frac{m}{2\times a\times b}\times(a^2\times b-a\times b+b^2-b+a\times b^2+a\times b-a^2+a)\cr&=\frac{m}{2\times a\times b}\times [a\times b\times (a-b)-(a+b)\times (a-b)+(a-b)]\cr&=\frac{m}{2\times a\times b}\times (a-b)\times (a\times b-a-b+1)\cr&=\frac{m}{2\times a\times b}\times (a-b)\times (a-1)\times (b-1)\end{aligned}$$
所以$(1)\ge(2)$，因而$a<b$时才能使得总比较次数最少。
### $2.$如果$x$为合数，就拆分为若干轮选美
不妨设$x=a\times b\ (1< b\le a <x)$，当前人数为$m$。
由结论$1$可以得到，先$b$后$a$比先$a$后$b$更好。再我们考虑每组$a\times b$个人的情况。
每组$a\times b$个人需要的比较次数：
$$\frac{m\times (a\times b-1)}{2} \kern{50pt} \cdots \cdots (3) \kern{-50pt}$$
与先$b$后$a$的情况相减：
$$\begin{aligned}(3)-(2)&=\frac{m}{2\times b}\times (a\times b^2-b-b^2+b-a+1)\cr
&=\frac{m}{2\times b}\times[(a-1)\times b^2-(a-1)]\cr
&=\frac{m}{2\times b}\times (a-1)\times (b+1)\times (b-1)\end{aligned}$$
因此，$(3)>(2)$，也就是说，拆成两组总是更优。
---
在证明完上述结论后，我们能得到一个初步的算法：
设$x=\prod_{i=1}^k p_i$，其中$p_i$为质数。那么依次化为$p_1,p_2,\cdots,p_k$个人为一组，可以使得最终的比较次数最少。
考虑区间筛素数的思想。即用$1\sim \sqrt{R}$内的所有质数，筛一遍$[L,R]$内的数字，并统计答案。具体来说，我们用$A_i$表示$f(i)$的贡献，$B_i$表示数字$i$目前还剩下多少。每次用$p$筛一遍含有因子$p$的数字，更新答案（$A_i\gets A_i+\frac{B_i\times (p-1)}{2},B_i\gets \frac{B_i}{p}$）。需要注意的是，每个数字可能有若干个质因子$p$，因此需要使用$p^2,p^3\cdots$继续处理。最后$B_i$剩下的要么是$1$，要么是它最大的质因数。处理一遍即可。
最后统计答案就可以了。时间复杂度与埃氏筛法相似，约为$\mathcal O(N \log \log N)$。
另外这里提供一个偷懒的小技巧：由于我们每次要访问$A_{l..r}$，而数组下标从$0$开始非常不方便。于是我们用指针$ * P$指向$A_0-l$，那么访问$P_x$就相当于访问了$A_{x-l}$。因为指针只表示地址，因此不会产生数组越界等问题。
## 参考代码
```
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
typedef long long LL;
const int INF =2147483647;
int qread(){
int w=1,c,ret;
while((c=getchar())> '9'||c< '0')
w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9')
ret=ret*10+c-'0';
return ret*w;
}
const int MAXN =5e6+3,MAXM=5e5+3,MOD=1e9+7;
int t,l,r,m,M1[MAXN],M2[MAXN],*A,*B,x=1,ans;
bool V[MAXM]; int P[MAXM],n;
int main(){
t=qread(),l=qread(),r=qread();
A=M1-l,B=M2-l,m=sqrt(r)+1;
up(2,m,i){
if(V[i]) continue; P[++n]=i;
up(2,m/i,j) V[i*j]=true;
}
up(l,r,i) B[i]=i;
up(1,n,i){
LL p=P[i]; while(p<=r){
int a=(l-1)/p+1,b=r/p;
up(a,b,j) A[p*j]=((LL)A[p*j]+(LL)B[p*j]*(P[i]-1)/2)%MOD,B[p*j]/=P[i];
p*=P[i];
}
}
up(l,r,i) A[i]=((LL)A[i]+(LL)B[i]*(B[i]-1)/2)%MOD;
up(l,r,i) ans=((LL)ans+(LL)x*A[i])%MOD,x=((LL)x*t)%MOD;
printf("%d\n",ans);
return 0;
}
```