题目链接：http://codeforces.com/gym/101981/attachments
题意：
令 $mul(l,r) = \prod_{i=l}^{r}a_i$，且 $fac(l,r)$ 代表 $mul(l,r)$ 的不同素因子个数。求 $\sum_{i=1}^{n}\sum_{j=i}^{n}fac(i,j)$。
Input
The first line contains one integer n (1 \le n \le 10^6) — the length of the sequence.
The second line contains n integers ai (1 \le i \le n, 1 \le a_i \le 10^6) — the sequence.
Output
Print the answer to the equation.
Examples
standard input
10
99 62 10 47 53 9 83 33 15 24
standard output
248
standard input
10
6 7 5 5 4 9 9 1 8 12
standard output
134
题解：
考虑每个质因子对于整体答案的贡献。
拿第二组样例算一算就不难发现：第 $p$ 个位置上的数，其包含的任意一个素因子，它原本应当产生的贡献有 $(n-p+1) \cdot p$，
但是考虑到若其前面出现过一样的素数，那么应当减去一些重复计算的区间。假设它前面的和它一样的素数，最后一次出现在 $q$ 位置，那么就应当减去 $(n-p+1) \cdot q$，即 $a[p]$ 包含的任意一个质因子其产生的贡献为 $(n-p+1) \cdot p - (n-p+1) \cdot q = (n-p+1) \cdot (p - q)$。
不妨用 $pos[i][k]$ 来存储每个素因子的 “$p$”，$pos[i][k-1]$ 存储每个素因子的 “$q$”。换句话说，$pos[i][k]$ 代表某个素因子 $i$ 在 $a[1 \sim n]$ 中第 $k$ 次“出现”的位置是 $pos[i][k]$；特别地，令 $pos[i][0]=0$。那么对于任意素因子 $i$，它对答案的贡献是 $(n-pos[i][k]+1) \cdot (pos[i][k]-pos[i][k-1])$。
我们可以对 $a[1 \sim n]$ 分解质因数，然后更新相应的 $pos[i][k]$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+; int n,a[maxn];
vector<int> pos[maxn];
void dec(int p)
{
int n=a[p];
for(int i=;i*i<=n;i++)
{
if(n%i==)
{
pos[i].push_back(p);
while(n%i==) n/=i;
}
}
if(n>) pos[n].push_back(p);
}
int main()
{
for(int i=;i<maxn;i++) pos[i].push_back(); scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
dec(i);
} ll ans=;
for(int i=;i<maxn;i++)
{
for(int k=;k<pos[i].size();k++)
ans+=(ll)(n-pos[i][k]+)*(pos[i][k]-pos[i][k-]);
}
cout<<ans<<endl;
}
分解质因数板子：
vector<int> dec(int n)
{
vector<int> p;
for(int i=;i*i<=n;i++)
{
if(n%i==)
{
p.push_back(i);
while(n%i==) n/=i;
}
}
if(n>) p.push_back(n);
return p;
}
交了一发，大概700ms多点过了，那我们能否加快一下速度呢？
我们可以先用线性筛筛出 $[1,1e6]$ 的素数，然后再做分解质因数：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+; int n,a[maxn];
vector<int> pos[maxn]; const int MAX=1e6;
int tot,prime[MAX/];
bool isPrime[MAX+];
void Screen() //欧拉筛
{
tot=;
memset(isPrime,,sizeof(isPrime));
isPrime[]=isPrime[]=;
for(int i=;i<=MAX;i++)
{
if(isPrime[i]) prime[tot++]=i;
for(int j=;j<tot;j++)
{
if(i*prime[j]>MAX) break;
isPrime[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
} void dec(int p)
{
int n=a[p];
for(int i=;i<tot && prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==)
{
pos[prime[i]].push_back(p);
while(n%prime[i]==) n/=prime[i];
}
}
if(n>) pos[n].push_back(p);
}
int main()
{
Screen();
for(int i=;i<tot;i++) pos[prime[i]].push_back(); scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
dec(i);
} ll ans=;
for(int i=;i<tot;i++)
{
for(int k=;k<pos[prime[i]].size();k++)
ans+=(ll)(n-pos[prime[i]][k]+)*(pos[prime[i]][k]-pos[prime[i]][k-]);
}
printf("%I64d\n",ans);
}
跑了大概400ms，还是快了不少的。