题解：UVA1718 Tile Cutting

· · 题解

咋没有人写倍增的 FFT？

令 V=\max\{r\}。

先预处理出 f(m)。对于一个平行四边形，可以用一个矩形框起来，四个点的坐标分别是 (a,0),(0,c),(a+b,d),(b,c+d)。

这个平行四边形的面积就是 (a+b)(c+d)-ac-bd=ad+bc。因此 f(m)=\sum_{a,b,c,d}[ad+bc=m]。

因此答案就是对 ad+bc=m 计数。

先对 g(m)=\sum_{a,b}[ab=m] 计数，发现是 m 的因数个数，可以通过埃氏筛在 O(V\log V) 的时间复杂度内求出。

发现 f(m)=\sum g(i)g(m-i)，是一个卷积的形式，使用 FFT，求多项式 g 的平方就能得到 f。

然后就是静态 RMQ 问题，这个可以使用 ST 表解决。

时间复杂度 O(V\log V+n)。

#include<bits/stdc++.h>
#define ll long long
#define db long double
using namespace std;
constexpr db eps=1e-8,pi=3.14159265358979323846;
constexpr ll R=5e5+5,maxn=2e6+10;
struct compx{
    db x,y;
}f[maxn];
compx operator +(compx a,compx b){
    return (compx){a.x+b.x,a.y+b.y};
}
compx operator -(compx a,compx b){
    return (compx){a.x-b.x,a.y-b.y};
}
compx operator *(compx a,compx b){
    return (compx){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
ll r[maxn],c[maxn],n,dp[maxn][22],ans[maxn];
void FFT(compx *a,ll lim,ll opt){
    for(int i=0;i<lim;i++){
        if(i<r[i])swap(a[i],a[r[i]]);
    }
    for(int len=1;len<lim;len<<=1){
        compx mul={1,0},w={cos(pi/len),opt*sin(pi/len)};
        for(int i=0;i<lim;i+=(len<<1)){
            mul={1,0};
            for(int j=0;j<len;j++){
                compx a0=a[i+j],a1=mul*a[i+j+len];
                a[i+j]=a0+a1;
                a[i+j+len]=a0-a1;
                mul=mul*w;
            }
        }
    }
    if(opt==-1){
        for(int i=0;i<lim;i++){
            a[i].x=(a[i].x/lim);
        }
    }
}
void mul(compx *a,ll len){
    ll lim=1,L=0;
    while(lim<=len+len){
        lim<<=1;
        L++;
    }
    for(int i=0;i<lim;i++){
        r[i]=(r[i>>1]>>1)|((i&1)<<(L-1));
    }
    FFT(a,lim,1);
    for(int i=0;i<lim;i++)a[i]=a[i]*a[i];
    FFT(a,lim,-1);
}
ll maxnum(ll a,ll b){
    return (ans[a]>=ans[b])?a:b;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;i<=R;i++){
        for(int j=i;j<=R;j+=i){
            c[j]++;
        }
    }
    for(int i=1;i<=R;i++){
        f[i]={1.0*c[i],0};
    }
    mul(f,R);
    for(int i=1;i<=R;i++){
        ans[i]=(ll)(f[i].x+0.5);
        dp[i][0]=i;
    }
    for(int j=1;j<22;j++){
        for(int i=1;i+(1<<(j-1))<=R;i++){
            //dp[i][j] 表示从 i 开始到 i+2^{j}-1 结束的最大下标
            dp[i][j]=maxnum(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
    cin>>n;
    while(n--){
        ll x,y;cin>>x>>y;
        ll k=__lg(y-x+1);
        ll cur=maxnum(dp[x][k],dp[y-(1<<k)+1][k]);
        cout<<cur<<" "<<ans[cur]<<"\n";
    }
    return 0;
}