题目链接：https://nanti.jisuanke.com/t/A2147
题目大意：有一个长度为n的序列a，定义mul(l, r)为区间[l, r]中a[i]的乘积，fac(l, r)为mul(l, r)不同素数因子的个数。求所有区间fac的和。
题解：先用样例二打表找规律，发现答案其实是所有区间中不同素数因子个数的和。
考察序列a中每个数对答案的贡献，不难发现，贡献为(i - vis[a[i]]) * (n - i + 1)。其中i表示第i个数(下标从1开始)，vis[a[i]]表示a[i]上一次出现的位置。
算贡献的式子可以这么理解：因为要算不同的素数的个数，如果这位置上的数是a[i]，它在之前出现过了，上一次出现的位置是vis[a[i]]，那么，在vis[a[i]]之前，现在遍历到的这个数a[i]是没有贡献的。 所以现在这个位置上的数a[i]就贡献了(i - vis[a[i]]) * (n - i + 1)。
预处理出所需要的素数，遍历一遍序列a，累加答案即可。
1 #include <iostream> 2 #include <vector> 3 #include <map> 4 #include <algorithm> 5 #include <queue> 6 #include <cstdio> 7 #include <cmath> 8 #include <string> 9 #include <set> 10 #include <complex> 11 #include <cstdio> 12 #include <cstring> 13 #include <stack> 14 #include <iomanip> 15 #include <bitset> 16 #include <typeinfo> 17 #include <random> 18 #include <unordered_map> 19 #include <unordered_set> 20 using namespace std; 21 22 const int maxn = 1e6 + 10; 23 const int N = 1e6 + 10; 24 25 int n, m, cnt_prime; 26 int a[maxn], p[maxn]; 27 int v[N]; 28 int prime[N], vis[maxn]; 29 vector<int> maze[maxn]; 30 31 void primes(int n){ 32 memset(v, 0, sizeof(v)); 33 cnt_prime = 0; 34 for(int i = 2; i <= n; i++){ 35 if(v[i] == 0){ 36 v[i] = i; 37 prime[++cnt_prime] = i; 38 } 39 for(int j = 1; j <= cnt_prime; j++){ 40 if(prime[j] > v[i] || prime[j] > n / i) break; 41 v[i * prime[j]] = prime[j]; 42 } 43 } 44 } 45 46 void divide(int n){ 47 m = 0; 48 for(int i = 1; prime[i] <= n / prime[i]; i++){ 49 if(n % prime[i] == 0){ 50 p[++m] = prime[i]; 51 while(n % prime[i] == 0) n /= prime[i]; 52 } 53 } 54 if(n > 1) p[++m] = n; 55 } 56 57 int main(){ 58 primes(1000000); 59 scanf("%d", &n); 60 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 61 for(int i = 1; i <= n; i++){ 62 divide(a[i]); 63 for(int j = 1; j <= m; j++){ 64 maze[i].push_back(p[j]); 65 } 66 } 67 long long tmp = 0, ans = 0; 68 for(int i = 1; i <= n; i++) vis[i] = 0; 69 70 for(int i = 1; i <= n; i++){ 71 for(int j = 0; j < (int)maze[i].size(); j++){ 72 int x = maze[i][j]; 73 ans += 1LL * (i - vis[x]) * (n - i + 1); 74 vis[x] = i; 75 } 76 } 77 printf("%lld\n", ans); 78 return 0; 79 }
原文：https://www.cnblogs.com/mrzhangziheng/p/11609065.html