2018-acmicpc-南京 J-Prime Game

题意

给定n个数，求出任意一段连续的数之间，不同质因子个数之和。
https://codeforces.com/gym/101981/problem/J

关键词

质因子、素数筛

思路

1. 打表求出每个数的质因数
2. 保存和计算每个数的每个质因子上一次出现的位置
3. 对每一个数的每一个质因子，求其出现次数之和

出现次数之和求法

• 设质因子前一次出现的位置+1为pre（初始值为1），当前位置为 i（从1开始）
• 则当前位置的一个质因子的出现次数为：cnt = (n - i + 1) * (i - pre + 1)
• ans = 每一个数的每一个质因子出现次数之和

为什么是(n-i+1)*(i-pre+1)

• 使用[ 6, 15, 10]为例打表：

  
  

• 解释：

  
  

以上图所示举例，图中在[pre, i]之间共有（i-pre+1）中情况，[i+1, n]之间有（n-i+1）种情况，二者的笛卡尔积（数量上相乘）即为[pre, n]之间的所有情况，在这些情况中，位于i位置的一个质因子都出现了一次。

已知pre表示该质因子上一次出现的位置，所以，包含pre之前位置的情况中，该质因子并不由i位置提供。

所以，i位置的某个质因子提供的次数为：(n - i + 1) * (i - pre + 1)。

代码

#include <bits/stdc++.h>

#define Debug 0
#define MAXN 1000056
#define MAXM 2600
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI 3.1415926535
#define pb push_back
#define SYNC ios::sync_with_stdio(false);
//#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt"
typedef long long ll;
typedef std::pair<int, int> Pair;

using namespace std;

int arr[MAXN];
bool isPrime[MAXN] = {1};
vector<int> primes[MAXN];
int pre[MAXN] = {0};
void init ()
{
    memset(isPrime, true, sizeof(isPrime));
    for (int i = 2; i < MAXN; ++i)
    {
        pre[i] = 1;
        if (isPrime[i])
        {
            primes[i].pb(i);
            for (int j = 2; j * i < MAXN; ++j)
            {
                int k = i * j;
                isPrime[k] = 0;
                primes[k].pb(i);
            }
        }
    }
}


int main ()
{

#ifdef FILE_IN
    freopen(FILE_IN, "r", stdin);
#endif
//    SYNC

    init();
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        vector<int> &vt = primes[arr[i]];
        int si = vt.size();
        for (int j = 0; j < si; ++j)
        {
            ll pr = pre[vt[j]];
            ans += 1LL*(i-pr+1)*(n-i+1);
            pre[vt[j]] = i+1;
        }
    }


    cout<<ans<<endl;

#ifdef FILE_IN
    fclose(stdin);
#endif

    return 0;
}