训练

admin管理员组

文章数量:1516870

训练

 题目链接

 想法:

将每个质因子它出现的下标用数组存起来。

这里以质因子2举例

0   1    2     3    4    5    6    7    8    9   10           (n个数)

                  2                      2                              假设2在这些地方出现了（下标为3，7的地方）

那么哪些子数组会包含质因子2呢?     

我是这样考虑的，【0~2】（3*（3+1）个子数组） 【4~6】（3*（3+1）个子数组） 【8~9】（同理）这三个区间的所有子数组一定都不包含2，统计出这些个数，然后用n*（n+1）/2减去这些数， 就能得到包含质因子2的子数组的个数。

可能想复杂了，先记录着吧，我要去学Java了，有更好的解法我再修改。

#include<bits/stdc++.h>
using namespace std;
const int N=200010,M=1000010,mod=1e9+7;
typedef long long LL;
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
map<int,vector<int>>num;
int n;
int a[N];
void solve(int x,int index)
{for(int i=2;i<=x/i;i++)if(x%i==0){while(x%i==0) x/=i;num[i].push_back(index);}if(x>1) num[x].push_back(index);
}
int main()
{ios;int T;cin>>T;while(T--){cin>>n;num.clear();for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++){int x=a[i];solve(x,i);}LL res=0;for(auto t:num){vector<int>&v=t.second;res+=(LL)n*(n+1)/2;for(int i=0;i<v.size();i++){int x=v[i];if(i==0) res-=(LL)x*(x+1)/2;else{x=v[i]-v[i-1]-1;res-=(LL)x*(x+1)/2;}}int x=n-v[v.size()-1]-1;res-=(LL)x*(x+1)/2;}cout<<res<<endl;}return 0;
}

本文标签： 训练