2018nanjing onsite J Prime Game(計數題）

題目連結：https://nanti.jisuanke.com/t/A2147

Given a sequence of nnn integers aia_iai​.

Let mul(l,r)=∏i=lrai\text{mul}(l, r) = \prod_{i = l}^{r} a_imul(l,r)=∏i=lr​ai​ and fac(l,r)\text{fac}(l, r) fac(l,r) be the number of distinct prime factors of mul(l,r)\text{mul}(l, r)mul(l,r).

Please calculate ∑i=1n∑j=infac(i,j)\sum_{i = 1}^{n}\sum_{j = i}^{n}\text{fac}(i, j)∑i=1n​∑j=in​fac(i,j)

Input

The first line contains one integer nnn (1≤n≤1061 \le n \le 10^61≤n≤106) —\text{—}— the length of the sequence.

The second line contains nnn integers aia_iai​ (1≤i≤n,1≤ai≤1061 \le i \le n, 1 \le a_i \le 10^61≤i≤n,1≤ai​≤106) —\text{—}— the sequence.

Output

Print the answer to the equation.

樣例輸入1

10

99 62 10 47 53 9 83 33 15 24

樣例輸出1

248

樣例輸入2

10

6 7 5 5 4 9 9 1 8 12

樣例輸出2

134

題目大意：任意一個區間的所有數的乘積有多少個不同的素因子，最後計算所有區間的個數的總和；

分析：

/// · ///

參考思路：https://blog.csdn.net/ftx456789/article/details/83116668

這題是計算貢獻值，

先篩出每個數的素因子，同時計算每個素因子對後面的數的貢獻值，若前面出現過，則從上一個位置開始計算，否則從最左邊開始計算

講下注意點吧

兩個int 相乘的時候要long long

~·~

代碼：

#include <bits/stdc++.h>

using namespace std;
#define ll long long 
const int N=1e6+5;

int prime[N];
unordered_map<int,int> mp;

void get_prime()
{
	for(int i=2;i<N;i++)
	{
		if(!prime[i])
		{
			prime[++prime[0]]=i;
		}
		for(int j=1;j<=prime[j]&&i*prime[j]<N;j++)
		{
			prime[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				break;
			}
		}
	}
}

int a[N];
int n;
ll ans=0;

void get_ap(int n,int nn,int id)
{
	for(int i=1;i<=prime[0]&&prime[i]*prime[i]<=n;i++)
	{
		if(n%prime[i]==0)
		{
			while(n%prime[i]==0)
				n/=prime[i];
			if(mp.count(prime[i]))
			{
				ans=ans+ (ll)(id-mp[prime[i]])*(nn-id);
				mp[prime[i]]=id;
			}
			else
			{
				mp[prime[i]]=id;
				ans=ans+ (ll)(id+1)*(nn-id);
			}
		}
	}
	if(n>1)
	{
		if(mp.count(n))
		{
			ans=ans+ (ll)(id-mp[n])*(nn-id);
			mp[n]=id;
		}
		else
		{
			mp[n]=id;
			ans=ans+ (ll)(id+1)*(nn-id);
		}
	}
	return ;
}

int main()
{
	
	get_prime();
	while(~scanf("%d",&n)){
		ans=0;
		mp.clear();
		for(int i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			get_ap(a[i],n,i);
		}


		printf("%lld\n",ans);
	
	}
	
	return 0;
}