网易算法岗4.21题解

A 删除平均数

题目大意大概是每次删掉比平均数大的，问删几次之后变成只有一个数。

先排序之后预处理前缀和，然后从后往前扫一下就行了，白给题。

#include<bits/stdc++.h>
using namespace std;
long long sum[101010],a[101010],s=0;
int main(){
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++)sum[i]=s+=a[i];
    long long temp=sum[n],res=0,cnt=n;
    for(i=n;i>0;i--){
        if(a[i]==a[1])break;
        if(a[i]*cnt<=temp)res++,temp=sum[i],cnt=i;
    }
    cout<<res;
}

B 最长递增祖先

本题要求每个节点往上的最远递增的祖先，这题确实可以建图然后dfs，不过那样写比较麻烦，直接用并查集+路径压缩就行了。

#include<bits/stdc++.h>
using namespace std;
int fa[101010];
int f(int x){return fa[x]==x?x:fa[x]=f(fa[x]);}
int a[101010],b[101010];
int main(){
    int n,i;
    cin>>n;
    for(i=1;i<=n;i++)fa[i]=i,cin>>a[i];
    for(i=2;i<=n;i++){
        cin>>b[i];
        if(a[b[i]]<a[i])fa[f(i)]=f(b[i]);
    }
    for(i=1;i<=n;i++)cout<<f(i)<<' ';
}

C 质数变换

题目大意是对于每个数可以变成大于它的最小质数或者小于它的最大质数，问最少多少次操作后所有数相等。

这道题考察了中位数定理，先排序然后最终变成的质数一定的离中位数最近的那个。如果有两个中位数，最终的质数就是取两个中位数最中间的那个质数。

要注意特判最开始所有数相等的情况，我因为没特判这个一直卡在90%过不去，结束之后自测了一个用例才发现。。

#include<bits/stdc++.h>
using namespace std;
int pr[101010],ok[101010],a[101010];
int main(){
    int n,i,j;
    ok[1]=1;
    for(i=2;i<=1e5+100;i++){
        if(ok[i])continue;
        for(j=i*2;j<=1e5+100;j+=i)ok[j]=1;
    }
    j=0;
    for(i=2;i<=1e5;i++)if(!ok[i])pr[j++]=i;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    if(a[0]==a[n-1])return cout<<0,0;
    long long res=0;
    int pid;
    if(n&1){
        int m=n/2;
        pid=lower_bound(pr,pr+j,a[m])-pr;
    }
    else{
        int m1=n/2-1,m2=m1+1;
        int pid1=lower_bound(pr,pr+j,a[m1])-pr;
        int pid2=upper_bound(pr,pr+j,a[m2])-pr-1;
        pid=pid1+pid2>>1;
    }
    for(i=0;i<n;i++){
        if(a[i]<pr[pid]){
            if(ok[a[i]])res++;
            int nowid=lower_bound(pr,pr+j,a[i])-pr;
            res+=pid-nowid;
        }
        else{
            int nowid=lower_bound(pr,pr+j,a[i])-pr;
               res+=nowid-pid;
        }
    }
    cout<<res;
}

D 小红的循环节长度

题目大意是给定一个分数，求循环节前面的长度和循环节的长度。

这个题需要一定的数学知识和数论能力。首先有个结论，循环节前面的长度取决于2和5因子数量的最大值。循环节长度取决于分母能被多少个连续9整数。例如7能被999999整除，所以分母7的循环节长度是6。然后根据欧拉定理，如果10和x互素，那么有 ，所以当x不含2和5的因子，只需要求出 即可（是欧拉函数，代表不超过x的且和x互素的数的个数）。

这样求出来的循环节长度不一定是最小，所以还需要枚举一下的因子，用快速幂验证一下是否能整除。

笔试的时候没开int128，结果爆longlong了，一直70%通过率，气死了。。。今天上午复盘的时候发现如果分母超1e9的话，快速幂的时候会爆longlong，只能用int128或者高精度之类的解决了，估计有两个测试用例是爆了longlong

#include<bits/stdc++.h>
using namespace std;
long long phi(long long x){
    long long i;
    long long res=x;
    for(i=2;i*i<=x;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)res=res/x*(x-1);
    return res;
}
long long power(__int128 a,long long b,long long p){
    __int128 res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int main(){
    long long p,q,i,c2=0,c5=0;
    cin>>p>>q;
    q/=__gcd(p,q);
    while(q%2==0)q/=2,c2++;
    while(q%5==0)q/=5,c5++;
    if(q==1)return cout<<-1,0;
    long long temp=phi(q);
    long long mi=1e16;
    for(i=1;i*i<=temp;i++){
        if(temp%i==0){
            if(power(10,i,q)==1)mi=min(mi,i);
            if(power(10,temp/i,q)==1)mi=min(mi,temp/i);  
        }
    }
    cout<<max(c2,c5)<<' '<<mi;
}