ProblemJ.primegame(质因数分解)xiaodangao

题目链接：https://codeforces.com/gym/101981
题意：给你n个数，让你求[1,n]所有区间的不同质因数个数；
解法：利用试除法分解合数，再分解过程中能求出区间[1,n]中一共有多少个不同素因数，我们假设从[1,n]的所有区间都存在全部不同素因数，等差数列求出区间数，再减去每一个质因数绝对不存在的每个区间；
代码如下：


/*************************************************************************
    > File Name: problemA.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2020年11月22日 星期日 13时01分44秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
using namespace std;
ll n,k;
const ll N = 1e6+10;
bool st[N];ll prime[N],tot,arr[N];
void iniv(){
    ll m = sqrt(N+0.5);st[1] = 1;
    for(ll i=2;i<=1000000;++i){
        if(!st[i]){
            prime[++tot] = i;
            if(i>m)continue;
            for(ll j=i*i;j<=1000000;j+=i)st[j] = 1;
        }
    }
}
bool vis[N];
ll  fac(ll l,ll r){
    ll ans = 0;
    memset(vis,0,sizeof vis);
    for(ll i=l;i<=r;++i){
        ll x = arr[i],now = 1;
        while(x!=1){
            if(x%prime[now]==0){
                if(vis[prime[now]]==false){
                    vis[prime[now]] = true;ans++;
                }
                x/=prime[now];
            }
            else now++;
        }
    }
    return ans;
}
ll G[N];
ll pop[N];
void solve(){
    scanf("%lld",&n);
    ll cnt = 0,ans = 0;
    for(ll i=1;i<=n;++i){
        scanf("%lld",&arr[i]);
        ll x = arr[i],now = 1;
        while(x>=prime[now]*prime[now]){
            if(x%prime[now]==0){
                if(G[prime[now]]==0){
                    pop[++cnt] = prime[now];
                }
                ll d = i - G[prime[now]] - 1;
                ans -= (d*(d+1))/2;
                G[prime[now]] = i;
                while(x%prime[now]==0)x/=prime[now];
            }
            now++;
        }
        if(x!=1){
            if(G[x]==0)pop[++cnt] = x;
            ll d = i - G[x] - 1;
            ans -= (d*(d+1))/2;
            G[x] = i;
        }
    }
    ll t = (ll)((n*(n+1))/2);
    ans += cnt*t;
    //printf("%lld %lld %lld\n",cnt,t,ans);
    for(ll i=1;i<=cnt;++i){
        ll d = n-G[pop[i]];
        ans -= (d*(d+1))/2;
    }
    printf("%lld\n",ans);
}
int main(){
    iniv();
    solve();
    return 0;
}

我们队的合数分解模板存在些问题，看来要给出来了(欧拉筛)


const int MAXN = 10000;
int prime[MAXN+1];
void getPrime(){
    memset(prime,0,sizeof prime);
    for(int i=2;i<=MAXN;++i){
        if(!prime[i])prime[++prime[0]] = i;
        for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;++j){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
ll factor[100][2];
int fatCnt;
int getFactors(ll x){
    fatCnt = 0;
    ll tmp = x;
    for(int i=1;prime[i]<=tmp/prime[i];++i){
        factor[fatCnt][1] = 0;
        if(tmp%prime[i]==0){
            factor[fatCnt][0] = prime[i];
            while(tmp%prime[i]==0){
                factor[fatCnt][1]++;
                tmp/=prime[i];
            }
            fatCnt++;
        }
    }
    if(tmp!=1){
        factor[fatCnt][0] = tmp;
        factor[fatCnt][1] = 1;
    }
    return fatCnt;
}

埃氏筛法见题解；需要注意的是，我们进行质因数分解，只需要分解到x>=prime[now]×prime[now]；最后如果x！=1那么x必是一个大于sqrt（x）的素数，有且只有一个，并且我们在分解的时候也不需要考虑x/prime[now]他是否是一个素数。
总结：这道题从一开始我们首先想到的是前缀和，因为区间个数是n*(n+1)/2个；并且一个区间内的不同质因数个数并不满足可加性，也就是说我们不能将他们放在一起去解题，这样会增大我们的解题难度，于是开始思考题目本身，题目本身给了我们一个很好的暗示，既然要求的是关于质因数的，我们为什么不挨个处理每一个质因数？(因为区间总数我们处理不了)今后要抓住题目所给的条件，不能够犯经验主义的错误；

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。