地址：http://acm.uestc.edu.cn/#/problem/show/1564
题目：
G - GC?(X,Y)
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 131071/131071KB (Java/Others)
One positive integer can be represented by the product of some prime numbers.
Sort the prime numbers, such like 60=2∗2∗3∗560=2∗2∗3∗5, 180=2∗2∗3∗3∗5180=2∗2∗3∗3∗5.
The GCPGCP(Greatest Common Prefix) of two positive integers is defined as the longest prefix of the multiplication of sorted prime numbers.
For example, GCP(60,180)=Longest_Prefix(2∗2∗3∗5,2∗2∗3∗3∗5)=2∗2∗3=12GCP(60,180)=Longest_Prefix(2∗2∗3∗5,2∗2∗3∗3∗5)=2∗2∗3=12.
Now, for a given array AiAi, calculate
∑1≤i<j≤NGCP(Ai,Aj)∑1≤i<j≤NGCP(Ai,Aj)
.
Input
The first line contains a number NN.
The second line contains NN integers AiAi.
1≤N≤105,1≤Ai≤1071≤N≤105,1≤Ai≤107
Output
Output the sum described above.
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 |
13 |
Hint
In the sample,
GCP(1,2)=GCP(1,8)=GCP(1,5)=GCP(1,10)=GCP(2,5)=GCP(8,5)=GCP(5,10)=1GCP(1,2)=GCP(1,8)=GCP(1,5)=GCP(1,10)=GCP(2,5)=GCP(8,5)=GCP(5,10)=1,
GCP(2,8)=GCP(2,10)=GCP(8,10)=2GCP(2,8)=GCP(2,10)=GCP(8,10)=2.
题解：
第一步肯定是先把所有数分解质因数。时间复杂度O(1e7+n*sqrt(n))
后面求最大公共前缀的做法有三种：
1.把所有质因数乘积表达式插入trie树中，然后O(n)遍历所有节点计算答案即可。
分析：1e7内的树最多分解成10个不同的质数乘积，25个可重复质数的乘积。
1e5个数分解成质因数后，所含的质数不会太多，应该在1e5~2e6之间（具体多少我也不清楚，队友算过，但我忘了）
可以对出现的质因数哈希一下，然后插入trie树中，每个节点最少记录两个值end，sum。
end：到该节点结尾的数的数量。
sum：经过该节点的数的数量（包括在该节点结尾的数）
由上可知trie树上的节点不会超过25n，一般情况远远小于这个数。
trie要选用动态分配内存的方法或者左儿子右兄弟的建树方法（也就是改成二叉树），不然mle。
不过我用动态分配内存的trie树时还是mle了，改了半天还没卡过去，其他队倒是好多人卡过去了（不过他们可能用的左儿子右兄弟的trie树）
左儿子右兄弟的trie树：
节省空间复杂度，除去了用节点，但是增加了时间复杂度。但只是增加时间复杂度的常数。（对于这题还是十分适用的）
遍历trie树即可计算答案，可用前缀和优化。
时间复杂度O(25n)，空间复杂度看trie树建法
2.把所有质因数乘积表达式当做字符串从小到大排序，然后对每个表达式二分最远匹配点，并计算答案。
排序函数cmp：根据两质因数乘积表达式第i个质数的大小，和质数个数排序。
二分：
对于第i个数，通过二分求出所有前缀所能匹配到的最远位置。
然后对于倒序计算这些前缀的贡献。
为什么要倒序，请看下例：
2*2，2*2*2,2*5
计算第一个数2*2的匹配位置数列是2,1.（从0开始计数）
此时计算第二个2所能匹配的位置的贡献（前缀）2*2 * （1-0）（最远匹配长度）
计算第一个2所能匹配的位置的贡献（前缀）2*2 * （2-1）（最远长度减上一个质数的匹配长度）
时间复杂度：O(nlogn+25nlogn)
3.哈希前缀
PS:比赛时一开始想二分算法，结果因为听到其他人用trie数过了，然后就一直怼trie然后。。。gg！
要是坚定自己的想法就好了，可惜了。。。
实现难度t：rie树远大于二分
（如果讲错请各位指教）
二分ac代码：
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long LL;
const int K=1e5+;
const int maxn=1e7+;
vector<int>num[K],va;
vector<LL>vb;
int n,pri[maxn],v[K],tol,tag[maxn];
LL ans;
bool cmp(const vector<int> &ta,const vector<int> &tb)
{
for(int i=,j=min(ta.size(),tb.size());i<j;i++)
if(ta[i]!=tb[i]) return ta[i]<tb[i];
return ta.size()<tb.size();
}
void init(void)
{
for (int i = ; i * i < maxn; i++)
{
if (tag[i]) continue;
for (int j = i; j * j < maxn; j++)
tag[i*j] = ;
}
for (int i = ; i < maxn; i++)
if (!tag[i])
pri[tol++] = i;
for(int i=; i<n; i++)
{
int t=v[i];
num[i].PB();
for(int j=; pri[j]*pri[j]<=t; j++)
{
if(v[i]%pri[j]) continue;
while(v[i]%pri[j]==) v[i]/=pri[j],num[i].PB(pri[j]);
}
if(v[i]>) num[i].PB(v[i]);
}
}
void bs(int x)
{
int sum=;
int l,r,mid,tmp=n-;
va.clear(),vb.clear();
for(int i=;i<num[x].size();i++)
{
l=x,r=tmp;
while(l<=r)
{
mid=(l+r)/;
if(num[mid].size()>i&&num[mid][i]==num[x][i])
tmp=mid,l=mid+;
else
r=mid-;
}
sum*=num[x][i];
va.PB(tmp),vb.PB(sum);
}
for(int i=num[x].size()-,ls=x;i>=;i--)
ans+=vb[i]*(va[i]-ls),ls=va[i];
}
int main(void)
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d",v+i);
init();
sort(num,num+n,cmp);
for(int i=;i<n;i++)
bs(i);
cout<<ans<<endl;
return ;
}
动态分配内存的trie树，未ac，mle16了，不想改成左儿子右兄弟了：
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
#define MAXNUM 27500
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=1e5+;
const int mod=1e9+;
const int maxn=1e7+; vector<int>num[K];
map<int,int>hs;
int n,pri[maxn],v[K],tol,tag[maxn];
int ths[K];
LL ans;
void make_prime()
{
for (int i = ; i * i < maxn; i++)
{
if (tag[i])
continue;
for (int j = i; j * j < maxn; j++)
tag[i*j] = ;
}
for (int i = ; i < maxn; i++)
if (!tag[i])
pri[tol++] = i;
}
void init()
{
for(int i=; i<n; i++)
{
int t=v[i];
num[i].PB();
for(int j=; pri[j]*pri[j]<=t; j++)
{
if(v[i]%pri[j]) continue;
while(v[i]%pri[j]==) v[i]/=pri[j],num[i].PB(pri[j]);
}
if(v[i]>) num[i].push_back(v[i]);
}
}
typedef struct Trie
{
int sum,ed;
Trie *next[MAXNUM];
}Trie;
Trie *root;
void TrieInit(int sz)
{
root = (Trie *)malloc(sizeof(Trie));
root->sum=root->ed=;
for(int i=;i<sz;i++)
root->next[i]=NULL;
for(int j=;j<n;j++)
{
Trie *tem=root;
for(int i=;i<num[j].size();i++)
{
//printf("x=%d:%d %d\n",j,num[j][i],hs[num[j][i]]);
if(tem->next[hs[num[j][i]]]==NULL)
{
Trie *cur = (Trie *)malloc(sizeof(Trie));
for(int k=;k<sz;k++)
cur->next[k]=NULL;
cur->sum=cur->ed=;
tem->next[hs[num[j][i]]]=cur;
}
tem = tem->next[hs[num[j][i]]];
tem->ed++;
}
tem->sum++;
}
}
void dfs(Trie *x,LL y,int sz)
{
Trie *tem = x,*cur;
LL ta=,tb=,ff=;
if(tem->ed-tem->sum>)
for(int i=;i<sz;i++)
if(tem->next[i]!=NULL)
{
cur=tem->next[i],ff++;
tb+=ta*cur->ed;
ta+=cur->ed;
if(cur->ed)dfs(cur,y*ths[i],sz);
}
if(ff>||tem->sum>)
ans+=y*tb+y*tem->sum*(tem->ed-tem->sum)+y*tem->sum*(tem->sum-)/2LL; } int main(void)
{
int cnt=;
scanf("%d",&n);
make_prime();
for(int i=;i<n;i++)
scanf("%d",v+i);
init();
for(int i=;i<n;i++)
{
//printf("x=%d: ",i);
for(int j=;j<num[i].size();j++,cnt++)
//printf("%d ",num[i][j]),
ths[cnt]=num[i][j];
//printf("\n");
}
sort(ths,ths+cnt);
int sz=unique(ths,ths+cnt)-ths;
for(int i=;i<sz;i++)
hs[ths[i]]=i;
TrieInit(sz);
for(int i=;i<sz;i++)
if(root->next[i]!=NULL)
dfs(root->next[i],ths[i],sz);
cout<<ans<<endl;
return ;
}