2018ICPC南京站Problem J. Prime Game

题意：

　　对于所有数字分解质因子，如果某个质因子在这个区间出现，则贡献为1，求所有质因子对所有区间做的贡献。

解析：

　　考虑如果所有全部区间都有这个质因子则这个质因子的贡献是n*（n+1）/2，对于任意因子，他的贡献等于区间个数减去他没有出现的区间个数，一个因子没有出现的区间就是出现的相邻两个位置之间。减去即可。

代码：

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <cstdio>

#include <queue>

#include <cmath>

#include <map>

#include <set>

using namespace std;

typedef long long ll;

const int maxn=1e6+;

int prime[maxn];

ll a[maxn];

int pr[maxn];

void getprime(){

    memset(pr,,sizeof(pr));

    for(int i=;i<=maxn;i++){

        if(!pr[i])pr[++pr[]]=i;

        for(int j=;j<=pr[]&&pr[j]<=maxn/i;j++){

            pr[pr[j]*i]=;

            if(i%pr[j]==)break;

        }

    }

}

int main(){

    int n;

    scanf("%d",&n);

    memset(prime,,sizeof(prime));

    for(int i=;i<=n;i++){

        scanf("%lld",&a[i]);

    }

    getprime();

    ll num=;

    for(int i=;i<=n;i++){

        for(int j=;pr[j]<=a[i]/pr[j];j++){

            if(a[i]%pr[j]==){

                while(a[i]%pr[j]==){

                    a[i]=a[i]/pr[j];

                }

                ll x=i-prime[pr[j]]-;

                num+=(x+)*x/;

                prime[pr[j]]=i;

            }

        }

        if(a[i]!=){

            ll x=i-prime[a[i]]-;

            num+=(x+)*x/;

            prime[a[i]]=i;

        }

    }

    ll ans=n;

    ans=ans*(ans+)/;

    ll nn=;

    for(int i=;i<maxn;i++){

        if(prime[i]){

            nn++;

            ll x=n-prime[i];

            num+=(x+)*x/;

            prime[i]=n+;

        }

    }

    //printf("%lld....\n",nn);

    ans=ans*nn;

    printf("%lld\n",ans-num);

    return ;

}

巴特西

2018ICPC南京站Problem J. Prime Game

题意：

解析：

代码：

最新文章

热门文章