题目链接：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=lrai 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=infac(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;
}
