Solution for Gym101981J

To solve this problem, we need to count for each prime factors, how many intervals include them.

First, let’s assume that all factors are distinct i.e. all factors only appears at one position. In this case, it’s easy to count the intervals that include them. For all primes at $p$ , there are $p\cdot(n-p+1)$ intervals including them.

However, one prime can appear multiple times so we need to substract the repeated intervals(interval contain the current position and last position). Formally, if a prime appears at $p$ and lastly appears at $q$ , it adds $(n-p+1)\cdot q$ to answer.

So our strategy is calculating all primes less than 1e6 first. Go through all the numbers and find their prime factors. Record the all appearance of each factor and calculate their contributions to the answer.

code:

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define pb push_back
#define ms(a, x) memset(a, x, sizeof(a))
 
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
const int MAXN=1e6+5;
int pri[MAXN],vis[MAXN],cnt=0;
vector<int> pos[MAXN];
void init() {
    for (int i = 2; i < MAXN; ++i) {
        if (!vis[i]) pri[cnt++] = i;
        for (int j = 0; j <cnt; ++j) {
            if (1ll * i * pri[j] >= MAXN) break;
            vis[i * pri[j]] = 1;
            if (i % pri[j]==0) break; 
        }
    }
    forn(i,cnt) pos[pri[i]].pb(0);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> a(n+1);
    for1(i,n) cin>>a[i];
    init();
    for1(i,n){
		for(int j=0;pri[j]*pri[j]<=a[i];j++){
			if(a[i]%pri[j]==0){
				pos[pri[j]].pb(i);
				while(a[i]%pri[j]==0) a[i]/=pri[j];
			}
		}
		if(a[i]>1) pos[a[i]].pb(i);
	}
    ll ans=0;
	forn(i,cnt){
		for(int j=1;j<pos[pri[i]].size();j++)
			ans+=ll(pos[pri[i]][j]-pos[pri[i]][j-1])*(n-pos[pri[i]][j]+1);
			
	}		
	cout<<ans;
    return 0;
}

Solution for Gym101981J - Prime Game