• 欢迎光临~

# 凹函数

## 题解

1. 答案在 (O(N^{2/3})) 数量级，这个可以由剪枝后向量的个数推出
2. 剪枝后的向量个数在 (O(N^frac 23)) 数量级

(sumlimits_Nsumlimits_N[gcd(X,Y)=1]cdot left [ maxleft ( sumlimits_X sumlimits_Y[gcd(x,y)=1]cdot x , sumlimits_X sumlimits_Y[gcd(x,y)=1]cdot y right ) leq N right ])

\$leq sumlimits_{1leq X,Yleq N} left [ maxleft ( sumlimits_{+infty}mu(d)d sumlimits_{X/d} sumlimits_{Y/d}x , sumlimits_{+infty}mu(d)d sumlimits_{X/d} sumlimits_{Y/d}y right ) leq N right ] \$

(sumlimits_{1leq X,Yleq N}[XYmax(X,Y)leq Theta(N)]=O(n^frac 23))

## 标准代码

### C++ 11

``````#include<stdio.h>
#include<bits/stdc++.h>
const int inf=0x3f3f3f3f;
void maxs(int& a,int b){ if(a<b)a=b; }
void mins(int& a,int b){ if(a>b)a=b; }
int gcd(int x,int y){ return y?gcd(y,x%y):x; }
int n;
namespace sol{//n^4
int vf[307][307];
void cal(){
for(int x=1;x<=n;++x){
for(int y=1;y<=n;++y)if(gcd(x,y)==1){
for(int i=n;i>=x;--i)
for(int j=n;j>=y;--j)maxs(vf[i][j],vf[i-x][j-y]+1);
}
}
}
int get(int x,int y){
return vf[x][y];
}
}
namespace sol{//n^(8/3)logn
int s[4007];
int f[4007][4007];
void ins(int x,int y){
for(int i=n;i>=x;--i){
for(int j=n;j>=y;--j){
maxs(f[i][j],f[i-x][j-y]+1);
}
}
}
void cal(){
for(int i=1;i<=n;++i){
int s1=0;
for(int j=1;j<=n&&s[j]<=n*2;++j){
if(gcd(i,j)==1){
s1+=i+j;
if(s[j]+s1<=n*2)ins(i,j);
}
s[j]+=s1;
}
}
}
int get(int x,int y){
return f[x][y];
}
}
namespace sol{//n^(7/3)logn
int s[4007][2];
int fs[4007][407],sz[4007],o=0,err=0;
void ins(int x,int y){
for(int i=n;i>=x;--i){
bool st=0;
for(int j=0;j<=sz[i-x];++j){
int a=fs[i-x][j]+y;
if(a>n)break;
mins(fs[i][j+1],a);
}
if(fs[i][sz[i]+1]<inf)fs[i][++sz[i]+1]=inf;
}
}
int get(int x,int y){
return std::upper_bound(fs[x],fs[x]+sz[x]+1,y)-fs[x]-1;
}
void cal(){
for(int i=0;i<=n;++i)fs[i][1]=inf;
for(int i=1;i<=n;++i){
int s0=0,s1=0;
for(int j=1;j<=n&&std::max(s[j][0],s[j][1])<=n;++j){
if(gcd(i,j)==1){
s0+=i;
s1+=j;
if(std::max(s[j][0]+s0,s[j][1]+s1)<=n)ins(i,j);
}
s[j][0]+=s0;
s[j][1]+=s1;
}
}
}
}
int q,qs[10007][2];
int main(){
n=1;
assert(scanf("%d",&q)==1);
assert(1<=q&&q<=10000);
for(int i=0;i<q;++i){
assert(scanf("%d%d",qs[i],qs[i]+1)==2);
assert(qs[i][0]>=1&&qs[i][0]<=3000);
assert(qs[i][1]>=1&&qs[i][1]<=3000);
n=std::max(n,std::max(qs[i][0],qs[i][1]));
}
using namespace sol3;
cal();
for(int i=0;i<q;++i)printf("%dn",get(qs[i][0],qs[i][1])+1);
return 0;
}

``````