Gym 101981J - Prime Game - [数学题][线性筛+分解质因数][2018-2019 ACM-ICPC Asia Nanjing Regional Contest Problem J]

题目链接：http://codeforces.com/gym/101981/attachments

题意：

令 $mul(l,r) = \prod_{i=l}^{r}a_i$，且 $fac(l,r)$ 代表 $mul(l,r)$ 的不同素因子个数。求 $\sum_{i=1}^{n}\sum_{j=i}^{n}fac(i,j)$。

Input
The first line contains one integer n (1 \le n \le 10^6) — the length of the sequence.
The second line contains n integers ai (1 \le i \le n, 1 \le a_i \le 10^6) — the sequence.

Output
Print the answer to the equation.

Examples
standard input
10
99 62 10 47 53 9 83 33 15 24

standard output
248

standard input
10
6 7 5 5 4 9 9 1 8 12

standard output

134

题解：

考虑每个质因子对于整体答案的贡献。

拿第二组样例算一算就不难发现：第 $p$ 个位置上的数，其包含的任意一个素因子，它原本应当产生的贡献有 $(n-p+1) \cdot p$，

但是考虑到若其前面出现过一样的素数，那么应当减去一些重复计算的区间。假设它前面的和它一样的素数，最后一次出现在 $q$ 位置，那么就应当减去 $(n-p+1) \cdot q$，即 $a[p]$ 包含的任意一个质因子其产生的贡献为 $(n-p+1) \cdot p - (n-p+1) \cdot q = (n-p+1) \cdot (p - q)$。

不妨用 $pos[i][k]$ 来存储每个素因子的 “$p$”，$pos[i][k-1]$ 存储每个素因子的 “$q$”。换句话说，$pos[i][k]$ 代表某个素因子 $i$ 在 $a[1 \sim n]$ 中第 $k$ 次“出现”的位置是 $pos[i][k]$；特别地，令 $pos[i][0]=0$。那么对于任意素因子 $i$，它对答案的贡献是 $(n-pos[i][k]+1) \cdot (pos[i][k]-pos[i][k-1])$。

我们可以对 $a[1 \sim n]$ 分解质因数，然后更新相应的 $pos[i][k]$。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+;

int n,a[maxn];

vector<int> pos[maxn];

void dec(int p)

{

    int n=a[p];

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

    {

        if(n%i==)

        {

            pos[i].push_back(p);

            while(n%i==) n/=i;

        }

    }

    if(n>) pos[n].push_back(p);

}

int main()

{

    for(int i=;i<maxn;i++) pos[i].push_back();

    scanf("%d",&n);

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

    {

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

        dec(i);

    }

    ll ans=;

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

    {

        for(int k=;k<pos[i].size();k++)

            ans+=(ll)(n-pos[i][k]+)*(pos[i][k]-pos[i][k-]);

    }

    cout<<ans<<endl;

}

分解质因数板子：

vector<int> dec(int n)

{

    vector<int> p;

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

    {

        if(n%i==)

        {

            p.push_back(i);

            while(n%i==) n/=i;

        }

    }

    if(n>) p.push_back(n);

    return p;

}

交了一发，大概700ms多点过了，那我们能否加快一下速度呢？

我们可以先用线性筛筛出 $[1,1e6]$ 的素数，然后再做分解质因数：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e6+;

int n,a[maxn];

vector<int> pos[maxn];

const int MAX=1e6;

int tot,prime[MAX/];

bool isPrime[MAX+];

void Screen() //欧拉筛

{

    tot=;

    memset(isPrime,,sizeof(isPrime));

    isPrime[]=isPrime[]=;

    for(int i=;i<=MAX;i++)

    {

        if(isPrime[i]) prime[tot++]=i;

        for(int j=;j<tot;j++)

        {

            if(i*prime[j]>MAX) break;

            isPrime[i*prime[j]]=;

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

        }

    }

}

void dec(int p)

{

    int n=a[p];

    for(int i=;i<tot && prime[i]*prime[i]<=n;i++)

    {

        if(n%prime[i]==)

        {

            pos[prime[i]].push_back(p);

            while(n%prime[i]==) n/=prime[i];

        }

    }

    if(n>) pos[n].push_back(p);

}

int main()

{

    Screen();

    for(int i=;i<tot;i++) pos[prime[i]].push_back();

    scanf("%d",&n);

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

    {

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

        dec(i);

    }

    ll ans=;

    for(int i=;i<tot;i++)

    {

        for(int k=;k<pos[prime[i]].size();k++)

            ans+=(ll)(n-pos[prime[i]][k]+)*(pos[prime[i]][k]-pos[prime[i]][k-]);

    }

    printf("%I64d\n",ans);

}

跑了大概400ms，还是快了不少的。

巴特西

Gym 101981J - Prime Game - [数学题][线性筛+分解质因数][2018-2019 ACM-ICPC Asia Nanjing Regional Contest Problem J]

最新文章

热门文章