[cf1285F]Classical

先枚举$d=\gcd$，然后暴力枚举所有$d$的倍数，相当于求出若干个数中最大的互素对

假设选出的数依从大到小排序后为$a_{i}$，令$g_{i}=\min_{(a_{i},a_{j})=1}j$，则答案为$\max a_{i}\cdot a_{g_{i}}$

考虑一种比较奇怪的计算$g_{i}$的方式，先求出$tot=\sum_{j=1}^{n}[(a_{i},a_{j})=1]$，然后从$n$到1依次删除，直到删除的数中与$a_{i}$互素的数达到了$tot$个

关于$tot$的计算可以用莫比乌斯反演，即化简为$\sum_{d|a_{i}}\mu(d)\sum_{j=1}^{n}[d|a_{j}]$，记后面的式子为$f(d)$，可以在插入$a_{j}$时处理，那么就可以做到”均摊“单次插入/删除/询问$o(\ln n)$

之后考虑从$n$到1依次去删除，复杂度为$o(n-g_{i})$，但注意到若$g_{i}\ge g_{i-1}$那么没有意义，因此从$g_{i-1}$开始统计（即令$n=g_{i-1}$）就可以做到$o(n\ln^{2}n)$了（枚举$d$+计算$tot$的调和级数和gcd）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 vector<int>v,d[N];

 5 int n,x,vis[N],mu[N],p[N],f[N];

 6 long long ans;

 7 int gcd(int x,int y){

 8     if (!y)return x;

 9     return gcd(y,x%y);

10 }

11 void update(int k,int p){

12     for(int i=0;i<d[k].size();i++)f[d[k][i]]+=p;

13 }

14 int query(int k){

15     int ans=0;

16     for(int i=0;i<d[k].size();i++)ans+=mu[d[k][i]]*f[d[k][i]];

17     return ans;

18 }

19 int main(){

20     mu[1]=1;

21     for(int i=2;i<N-4;i++){

22         if (!vis[i]){

23             p[++p[0]]=i;

24             mu[i]=-1;

25         }

26         for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){

27             vis[i*p[j]]=1;

28             if (i%p[j])mu[i*p[j]]=-mu[i];

29             else{

30                 mu[i*p[j]]=0;

31                 break;

32             }

33         }

34     }

35     scanf("%d",&n);

36     memset(vis,0,sizeof(vis));

37     for(int i=1;i<=n;i++){

38         scanf("%d",&x);

39         vis[x]=1;

40     }

41     for(int i=1;i<N-4;i++)

42         for(int j=i;j<N-4;j+=i)d[j].push_back(i);

43     for(int i=1;i<N-4;i++){

44         v.clear();

45         for(int j=i;j<N-4;j+=i)

46             if (vis[j])v.push_back(j/i);

47         int m=v.size();

48         for(int j=0;j<m;j++)update(v[j],1);

49         for(int j=m-1,k=0;j>=0;j--){

50             int sum=query(v[j]);

51             while (sum){

52                 if (gcd(v[j],v[k])==1){

53                     sum--;

54                     ans=max(ans,1LL*v[j]*v[k]*i);

55                 }

56                 update(v[k++],-1);

57             }

58             if (!j)

59                 while (k<m)update(v[k++],-1);

60         }

61     }

62     printf("%lld",ans);

63 }

巴特西

[cf1285F]Classical

最新文章

热门文章