【线性筛】ccpc黑龙江省赛 F

淡淡的烟草味﹌ 2024-03-26 15:23 55阅读 0赞

**第一次vp省赛，只出了三题，很寄啊**

[Problem - F - Codeforces][]

题意：

![c657e658a05e907733e0fec862ad2399.png][]

思路：

题目一直在强调最小质因子，我们考虑边跑线性筛边求贡献

一、

对于第一种情况，即遇到的数是质数，贡献直接+1就好了

二、

对于第二种情况，即遇到的数是一个质数的幂次

通过迭代得到：f(p^k)=f(n)=p^(k/2)

三、

对于第三种情况，f(n)=p1^(k1/2)\*(n/p1^k1)

那这种情况的贡献就是用p1除完n之后的值\*p1^k1，p1^k2就转化成第二种情况

然后去考虑线性筛

1.质数的时候贡献+1

2.当i%prime\[j\]==0的时候，prime\[j\]不是i的最小质因子，因此n=i\*prime\[j\]具有prime\[j\]的幂次，也有别的质因子，所以就对应了第三种情况

3.当i%prime\[j\]!=0的时候，此时prime\[j\]是i的最小质因子，同样也是第三种情况。因为是用最小质因子去筛的，因此最小质因子的指数k1=1，贡献就是 p1^(1/2)\*(i\*p1)/p1^1=i

Code：

#include <bits/stdc++.h>
    using namespace std;
    using i64 = long long;
    const int mxn=1e7+10;
    
    int n,len=0;
    i64 ans=1;
    int prime[mxn],vis[mxn];
    i64 ksm(int a,int b){
        i64 res=1;
        while(b){
            if(b&1) res=(res*a);
            a=(a*a);
            b>>=1;
        }
        return res;
    }
    void init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i,ans++;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0){
                    i64 tmp=i*prime[j];
                    int s=0;
                    while(tmp%prime[j]==0) tmp/=prime[j],s++;
                    ans+=tmp*ksm(prime[j],s/2);
                    break;
                }
                ans+=i;
            }
        }
    }
    void solve(){
        cin>>n;
        init(n);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/gym/103107/problem/F
[c657e658a05e907733e0fec862ad2399.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/898dce1dfd4c466d9ee54b9bdce83b21.png