UVA1655 考试 Exam

· · 题解

思路：

相当于求三元组 i \times j \times k \le n 的数量。

考虑枚举 i，那么 j 的范围只能在 [1,\lfloor \frac{n}{i} \rfloor]，此时可能的 k 的数量就是 \lfloor \frac{n}{i \times j} \rfloor，则答案为：

\sum_{i=1}^n \sum_{j=1}^{\lfloor \frac{n}{i} \rfloor} \lfloor \frac{n}{i \times j} \rfloor

后面那串式子可以数论分块计算，定义：

F(n)=\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor=2 \times \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \lfloor \frac{n}{i} \rfloor - \lfloor \sqrt{n} \rfloor^2

那么原式可以化为：

\sum_{i=1}^n F(\lfloor \frac{n}{i} \rfloor)

发现也可以数论分块，于是数论分块套数论分块就做完了。

时间复杂度约为 O(T \times N^{\frac{3}{4}}) 往上。

但是在本题的极限数据下会超时，考虑进行优化。

注意到：

F(n)=\sum_{i=1}^n d(i)

其中 d(i) 表示 i 的约数个数，那么可以先线性筛出 N^{\frac{2}{3}} 以内的值，计算其前缀和就可以预处理出 F 的值。

此时时间复杂度优化到了 O(N^{\frac{2}{3}})。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=2.3e7+7;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
int T,cnt;
int P[N],F[N];
ll n,A[N];
bitset<N+5> f;
inline ll Fun(ll n){
    if(n<N)
      return A[n];
    ll B=sqrt(n),ans=0;
    for(int i=1;i<=B;i++)
      ans+=n/i;
    return 2ll*ans-B*B;
}
inline void init(){
    A[1]=1;
    for(int i=2;i<N;i++){
        if(!f[i]){
            P[++cnt]=i;
            A[i]=2;
            F[i]=1;
        }
        for(ll j=1;j<=cnt&&i*P[j]<N;j++){
            f[i*P[j]]=1;
            if(i%P[j]){
                F[i*P[j]]=1;
                A[i*P[j]]=A[i]*2ll;
            }
            else{
                F[i*P[j]]=F[i]+1;
                A[i*P[j]]=A[i]/(F[i]+1)*(F[i]+2);
                break;
            }
        }
    }
    for(int i=2;i<N;i++)
      A[i]+=A[i-1];
}
inline ll solve(ll n){
    ll ans=0,B=sqrt(n),cnt=n/B+B-1;
    ll l=0,r=0,lj=0,rj=0;
//  cerr<<r<<'\n';
    for(ll i=0;i<cnt;i++){
        r=i<B?n/(i+1):l-1,rj=Fun(r);
        ans+=i?(n/l)*(lj-rj):n;
        l=r,lj=rj;
    }
    return ans;
}
int main(){
//  freopen("A.in","r",stdin);
//  freopen("A.out","w",stdout);
    init();
    while(~scanf("%lld",&n))
      printf("Case %d: %lld\n",++T,solve(n));
    return 0;
}