Day6

GSRgsrgsr · 2023-07-29 19:36:32 · 个人记录

前言：数学场被巨佬们吊打了(悲）

T1

考虑类似线性筛的过程，将p_1,p_2,...,p_m的倍数打上标记，然后扫一遍统计答案即可

O(n)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e7+5; 
const int M=1e5+5;
int p[M];
bool vis[N];
bool cmp(int x,int y){
    return x<y;
}
signed main(){
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&p[i]);
        vis[p[i]]=true;
    }
    sort(p+1,p+m+1,cmp);
    for(int i=2;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(1ll*i*p[j]>n)break;
            vis[p[j]*i]=true;
            if(i%p[j]==0)break;
        }
    }
    for(int i=1;i<=n;++i)if(vis[i])ans++;
    printf("%d",ans);
    return 0;
}

T2

还是考虑在线性筛的过程中维护一个i的最大因子fa[i]以及点i在树上的深度（1到i的路径上有几条边）dep[i],然后扫一遍将fa[i]变成i的父亲。对于每个询问u,v(dep[u]<=dep[v]),有两种情况：

1.u是v的祖先,答案显然是dep[v]-dep[u]

2.否则答案是dep[u]+dep[v]-2*dep[LCA(u,v)]

现在问题就成了如何求LCA了。

由于N太大，倍增数组肯定开不下，所以我们只能暴力往上跳，复杂度为O(n\sqrt{q})，TLE。。。

真的吗？！！

实际上，每次跳父亲是除以一个最大的因子，所以实际的复杂度是O(n+q*d(n)),根据lxl讲的经典结论，d(n)这东西非常小，所以肯定可以过

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e7+5; 
const int M=1e5+5;
int p[M];
bool vis[N];
bool cmp(int x,int y){
    return x<y;
}
signed main(){
    int n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&p[i]);
        vis[p[i]]=true;
    }
    sort(p+1,p+m+1,cmp);
    for(int i=2;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(1ll*i*p[j]>n)break;
            vis[p[j]*i]=true;
            if(i%p[j]==0)break;
        }
    }
    for(int i=1;i<=n;++i)if(vis[i])ans++;
    printf("%d",ans);
    return 0;
}

T3

先考虑一个子问题:计算\sum_{x=1}^{n}\sum_{y=x}^{n}[x\mid y]

枚举x,答案显然为\sum_{x=1}^{n}\lfloor \frac{n}{x} \rfloor