题解：P10700 [SNCPC2024] 猜质数 II

BuQiuRu4587 · 2024-07-09 08:47:53 · 题解

难点在于看懂题意，场上硬是瞪了十分钟才看懂题，之后就比较套路，最后只有我们队和 rk1 过了这个题估计就是因为大部分人不想看题。

首先不管这个 f 函数的定义，看看我们要求什么东西。

对于一个 (u,l) 的询问，我们要求的应该是以下这个式子：

换一下求和顺序：

由于 a 值域是 10^6，而且所有 f(i,j)\not =0 要满足 i\le j。所以 \sum\limits_{i=1}^{10^6}f(i,a_j) 相当于是把所有有值的 f(i,a_j) 都枚举了一遍。而通过观察，可以发现 \sum\limits_{i=1}^{10^6}f(i,a_j)=-a_id(a_i)+\varphi(a_i)\times u。其中 d(x) 表示 x 的因数个数。

那么所求为：

将 \varphi(a_i)\times u-a_id(a_i) 看做自变量是 u 的一次函数 f_i(u)，所求为：

设 s_i(u)=\sum\limits_{j=1}^i f_j(u)。式子可以写成：

直接将操作离线，从后向前枚举查询的 l，问题等价于插入一个一次函数，查询一个位置上的最大点值，我们使用李超线段树解决，再使用线性筛预处理出 d,\varphi 函数，复杂度是 O(n\log V+V)。

场上由于赶时间，线性筛代码是我从网上贺的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed prime[18000005], tot,phi[18000005];
bool isprime[18000005];
signed num[18000005]; //最小质因子p1组成的等比序列 p1^0+p1^1+...+p1^r1
int d[18000005]; //约数和
void shai(int n=18000000) {
    d[1] = 1; // 1的约数只有自己，约数和是1
    phi[1]=1;
    for (int i = 2; i <= n; i++) {
        if (!isprime[i]) {
            prime[tot++] = i;
            phi[i]=i-1;
            d[i] = num[i] = i + 1; // 1和自身是约数，约数和为i+1; 同时因为i是质数，所以只有一个分拆项,并且分拆项内容=pj^0+pj^1=1+pj=1+i
        }
        for (int j = 0; prime[j] * i <= n&&j<tot; j++) {
            isprime[i * prime[j]] = true;
            if (i % prime[j]) {
                d[i * prime[j]] = d[i] * d[prime[j]]; //积性函数
                num[i * prime[j]] = prime[j] + 1;
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            } else {
                d[i * prime[j]] = d[i] / num[i] * (num[i] * prime[j] + 1);
                num[i * prime[j]] = num[i] * prime[j] + 1;
                phi[i*prime[j]]=phi[i]*prime[j]; 
                break;
            }
        }
    }
}   
struct line{
    int k,b;
    signed id;
    line(){
        k=id=0;
        b=-1e18;
    }
}sum[500005],tree[500005*50];
signed ls[500005*50],rs[500005*50],cnt,root;
#define mid ((l+r)>>1)
int F(line l,int x){
    return l.k*x+l.b;
}
bool cmp(line a,line b,int x){
    int A=F(a,x);
    int B=F(b,x);
    if(A!=B) return A>B;
    return a.id<b.id; 
}
int add(int now,int l,int r,line k){
    if(k.b==-1e18) return now;
    if(!now) now=++cnt;
    if(F(tree[now],mid)<=F(k,mid)) swap(tree[now],k);
    if(l==r) return now;
    if(F(tree[now],l)<=F(k,l)) ls[now]=add(ls[now],l,mid,k);
    if(F(tree[now],r)<=F(k,r)) rs[now]=add(rs[now],mid+1,r,k);
    return now;
}
line ret;
void ask(int now,int l,int r,int x){
    if(!now) return ;
    if(cmp(tree[now],ret,x)) ret=tree[now];
    if(l==r) return ;
    if(mid>=x) ask(ls[now],l,mid,x);
    else ask(rs[now],mid+1,r,x);
}
#undef mid
int n,q,a[500005];
vector<pair<int,int> > vec[500005];
int ans[500005],id[500005];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q;
    shai();
    sum[0].k=sum[0].b=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i].b=-d[a[i]]*a[i];
        sum[i].k=phi[a[i]];
        sum[i].b+=sum[i-1].b;
        sum[i].k+=sum[i-1].k;
        sum[i].id=i;
    }
    for(int i=1;i<=q;i++){
        int u,l;cin>>u>>l;
        vec[l].push_back(make_pair(u,i));
    }
    for(int i=n;i;i--){
        root=add(root,1,18000000,sum[i]);
        for(auto u:vec[i]){
            ret.b=-1e18;
            ret.id=ret.k=0;
            ask(root,1,18000000,u.first);
            ans[u.second]=F(ret,u.first)-F(sum[i-1],u.first);
            id[u.second]=ret.id;
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<' '<<id[i]<<'\n';
    }
}