喵哈哈村的魔法考试 Round #10 (Div.2) E

喵哈哈村与哗啦啦村的大战（五）

发布时间: 2017年3月27日 10:55   时间限制: 1000ms   内存限制: 128M

描述

喵哈哈村因为和哗啦啦村争夺稀有的水晶资源，展开了激烈的战斗！

喵哈哈村为了选拔出优秀的战士，于是出了一道题：

喵哈哈村定义GCP，叫做最大质因数前缀，比如60=2*2*3*5，180=2*2*3*3*5，那么GCP(60,180)=2*2*3=12。

现在给你n个数，请你计算sum，sum计算方式如下：

sum = 0
for i=1 to n
  for j=i+1 to n
    sum = sum + GCP(a[i],a[j])

输出答案即可。

输入

本题包含若干组测试数据。
第一行一个整数n，表示整数的个数。
第二行n个整数a[i]，表示数的大小。

满足 1<=n<=100000 1<=a[i]<=1e7

输出

输出答案即可。

样例输入1 复制

5
1 2 8 5 10

样例输出1

13

题解：这个题目想了很久啊。。。按照卿学姐的解释，用一个数组m[i]来表示前缀为i 的个数，因为我们的目标是找到最大的前缀和，所以在搜之前要reverse一下。比如对于12=2*2*3；gcp为2
的个数就是m[2]-m[4]（这里有个知识点啊。。。任意一个数a可以唯一写成表达式a=p1

^b1

*p2

^{b2...其中p1和p2都是质数}

）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
map<int, int>m;
int n;

int main(){
    while(cin>>n){
        long long ans=0;
        m.clear();
        for(int i=0; i<n; i++){
            scanf("%d", &a[i]);
        }
        for(int i=0; i<n; i++){
            vector<int>tmp;
            int now=1;
            tmp.push_back(now);
            for(int j=2; j*j<=a[i]; j++){
                while(a[i]%j==0){
                    now*=j;
                    tmp.push_back(now);
                    a[i]/=j;
                }
            }
            if(a[i]!=1){
                now*=a[i];
                tmp.push_back(now);
            }
            reverse(tmp.begin(), tmp.end());　　　　//这里reverse一下，前缀从大到小开始判断
            long long sum=0;
            for(int j=0; j<tmp.size(); j++){
                ans+=1ll*tmp[j]*(1ll*(m[tmp[j]]-sum));　　//当前的前缀为tmp[j]的个数减去上一个前缀更大的个数（就是要减去已经计算了更大前缀的数，防止重复计算）
                sum=m[tmp[j]];
                m[tmp[j]]++;
            }
        }    
        cout<<ans<<endl;
    }    
    return 0;
}