2018南京区域赛J-Prime Game【素数分解】
发布时间
阅读量：
阅读量
思路：我们需要计算每个质因数的贡献。首先对所有素数进行筛选，在此基础上对每个数字进行质因数分解。从而我们可以获得该数字所包含的素因子。接着我们需要计算每个因子在区间内的贡献程度。具体可以看代码，在此基础之上我们还需要持续更新这些素因子的位置信息。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
int prime[maxn], a[maxn];
int pre[maxn];
ll ans = 0;
int n;
void getprime()
{
prime[0] = 0;
for(int i = 2; i < maxn; ++i)
{
if(!a[i])
{
prime[++prime[0]] = i;
for(int j = i * 2; j < maxn; j += i)
a[j] = 1;
}
}
}
void slove(int x, int idx)
{
for(int i = 1; i < prime[0] && prime[i] * prime[i] <= x; ++i)
{
if(x % prime[i] == 0)
{
int pos = pre[prime[i]];
int l = idx - pos;
int r = n - idx + 1;
ans += (ll)l * r;
pre[prime[i]] = idx;
while(x % prime[i] == 0)
x /= prime[i];
}
}
if(x > 1)
{
int pos = pre[x];
int l = idx - pos;
int r = n - idx + 1;
ans += (ll)l * r;
pre[x] = idx;
}
}
int main()
{
getprime();
memset(pre, 0, sizeof(pre));
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for(int i = 1; i <= n; ++i)
{
slove(a[i], i);
}
cout << ans << endl;
return 0;
}全部评论 (0)
还没有任何评论哟~