题意
给定n个数,求出任意一段连续的数之间,不同质因子个数之和。
https://codeforces.com/gym/101981/problem/J
关键词
质因子、素数筛
思路
- 打表求出每个数的质因数
- 保存和计算每个数的每个质因子上一次出现的位置
- 对每一个数的每一个质因子,求其出现次数之和
出现次数之和求法
- 设质因子前一次出现的位置+1为pre(初始值为1),当前位置为 i(从1开始)
- 则当前位置的一个质因子的出现次数为:cnt = (n - i + 1) * (i - pre + 1)
- ans = 每一个数的每一个质因子出现次数之和
为什么是(n-i+1)*(i-pre+1)
-
使用[ 6, 15, 10]为例打表:
-
解释:
以上图所示举例,图中在[pre, i]之间共有(i-pre+1)中情况,[i+1, n]之间有(n-i+1)种情况,二者的笛卡尔积(数量上相乘)即为[pre, n]之间的所有情况,在这些情况中,位于i位置的一个质因子都出现了一次。
已知pre表示该质因子上一次出现的位置,所以,包含pre之前位置的情况中,该质因子并不由i位置提供。
所以,i位置的某个质因子提供的次数为:(n - i + 1) * (i - pre + 1)。
代码
#include <bits/stdc++.h> #define Debug 0 #define MAXN 1000056 #define MAXM 2600 #define MOD 1000000007 #define INF 0x3f3f3f3f #define PI 3.1415926535 #define pb push_back #define SYNC ios::sync_with_stdio(false); //#define FILE_IN "I:\\acm-workspace\\CLion-Project\\in.txt" typedef long long ll; typedef std::pair<int, int> Pair; using namespace std; int arr[MAXN]; bool isPrime[MAXN] = {1}; vector<int> primes[MAXN]; int pre[MAXN] = {0}; void init () { memset(isPrime, true, sizeof(isPrime)); for (int i = 2; i < MAXN; ++i) { pre[i] = 1; if (isPrime[i]) { primes[i].pb(i); for (int j = 2; j * i < MAXN; ++j) { int k = i * j; isPrime[k] = 0; primes[k].pb(i); } } } } int main () { #ifdef FILE_IN freopen(FILE_IN, "r", stdin); #endif // SYNC init(); int n; cin >> n; ll ans = 0; for (int i = 1; i <= n; ++i) { cin >> arr[i]; vector<int> &vt = primes[arr[i]]; int si = vt.size(); for (int j = 0; j < si; ++j) { ll pr = pre[vt[j]]; ans += 1LL*(i-pr+1)*(n-i+1); pre[vt[j]] = i+1; } } cout<<ans<<endl; #ifdef FILE_IN fclose(stdin); #endif return 0; }