Project Euler 485

题目

Maximum number of divisors

Let $d(n)$ be the number of divisors of $n$.

Let $M(n,k)$ be the maximum value of $d(j)$ for $n \le j \le n+k-1$.

Let $S(u,k)$ be the sum of $M(n,k)$ for $1 \le n \le u-k+1$.

You are given that $S(1000,10)=17176$.

Find $S(100 000 000,100 000)$.

单调队列

单调队列是一种数据结构，通常用于维护区间的最值。

通常解决的问题是，给定一系列的区间$[l_1,r_1],[l_2,r_2],[l_3,r_3],\dots$的询问，分别求这些区间的最值。而且，$l_1\le l_2\le l_3\le \dots,r_1\le r_2\le r_3\le \dots$，即询问的$l_i,r_i$是不递减的。

那么考虑维护一个队列。一开始，询问的元素都被推进队列中，随着整个程序的运行，序列前面的元素已经过时，不再被询问，被弹出队列；而后面需要被询问的元素逐渐被推入队列中。但是，推入的新元素可能比旧元素更优，那么此时旧元素原地退出队列，让位给新元素，整个过程将会保持队列的单调性。队头的元素最优，队尾的元素最劣。

解决方案

$$S(N,K)=\sum_{i=1}^{N-K+1} \max_{j=i}^{i+K-1} \{d(j)\}$$

那么，询问值将是$[1,K],[2,K+1],[3,K+2],\dots$因此，使用单调队列来维护这些询问值。最终将每次维护结果的队头相加即可。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100000000,K=100000;
int f[N+4],v[N+4],pr[N/10+100],m=0;
int main(){
    f[1]=1;
    for(int i=2;i<=N;i++){
        if(v[i]==0) pr[++m]=i,v[i]=i,f[i]=2;
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>N/i) break;
            v[i*pr[j]]=pr[j];
            f[i*pr[j]]=(v[i]==pr[j]?f[i]*2-f[i/pr[j]]:f[i]*2);
        }
    }
    ll ans=0;
    deque<int>q;
    for(int i=K,j=1;i<=N;i++){
        while(!q.empty()&&i-q.front()>=K) q.pop_front();
        for(;j<=i;j++){
            while(!q.empty()&&f[j]>=f[q.back()]) q.pop_back();
            q.push_back(j);
        }
        ans+=f[q.front()];
    }
    printf("%lld\n",ans);
}