Prime Game --- Gym

题目

　　https://vjudge.net/problem/Gym-101981J

题意

　　定义：mul (l, r) = (∏_{i=l}^r) (a_i)

　　　　　fac (l, r) 为 mul (l, r) 的所有不同的质因子的个数

　　求 (∑_{i = 1}^n)(∑_{j = i}^n)fac (i, j)

题解

　　根据题目要求可以列出要求的内容

　　(a_1)

　　(a_1)*(a_2)　　　　　　(a_2)

　　(a_1)*(a_2)*(a_3)　　　　(a_2)*(a_3)　　(a_3)

　　……　　　　　　　　……　　　　　　……

　　(a_1)*(a_2)*……*(a_n)　　(a_2)*(a_3)*……*(a_n)　　　　(a_n)

　　要求的也就是上面这些个数的不同质因子个数之和，观察一下可以发现第 1 行到第 2 行就是将 2 项 (a_2) 加入结果，而对于答案的影响也就是新加入的 (a_2) 的质因子，由此可知第 i 行到第 i + 1 行对于答案的影响就是 (a_i) 的质因子 * i。那么我们记录下每个质因子最后是在第几层加入的，那么就知道原数中已经有几个数包含了这个质因子，那么新加入的质因子对于答案的贡献也就是 i - 该质因子之前的层数。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define met(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define bep(i, a, b) for(int i = a; i >= b; i--)
#define lowbit(x) (x&(-x))
#define MID (l + r) / 2
#define ls pos*2
#define rs pos*2+1
#define pb push_back
#define ios() ios::sync_with_stdio(0)

using namespace std;

const int maxn = 1e6 + 1010;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 123456789;

bitset<maxn> is_prime;
int prime[maxn], prime_cnt;
ll vis[maxn];
ll res, now;

void get_prime(int n) {
    is_prime[1] = 1;
    rep(i, 2, n) {
        if(!is_prime[i]) prime[++prime_cnt] = i;
        for(int j = 1; j <= prime_cnt && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
ll calc(ll n, ll x) {
    ll sum = 0;
    for(int i = 1; i <= prime_cnt && is_prime[n] && prime[i] <= n; i++) {
        while(n % prime[i] == 0) {
            sum += x - vis[prime[i]];
            vis[prime[i]] = x;
            n /= prime[i];
        }
    }
    if(!is_prime[n]) {
        sum += x - vis[n];
        vis[n] = x;
    }
    return sum;
}

int main() {
    ios();
    get_prime(maxn - 1);
    int n;
    cin >> n;
    rep(i, 1, n) {
        ll a;
        cin >> a;
        now += calc(a, i);
        res += now;
    }
    cout << res << endl;
    return 0;
}