官方题解——中位因数

H - 中位因数

​由于一个数字的所有因数是分布在 的左右两侧，而我们要求的是因数的中位数，也就是要求小于 而且能够整除的最大数字。首先我们用筛法算出 之内所有数字的因数个数，以及每个数字的最小质因子，如果一个数字的因数比较多，直接从 向下枚举找到第一个就是；如果一个数字的因数比较少，我们可以利用每个数字的最小质因子去找出所有的质因子，然后 枚举所有的因子。

我们还可以有一种想法，前一个想法是根据 来找中位因数，现在我们可以枚举因数来更新每个数字的中位因数里面小于等于 的那个。因为 最大为 ，因此只需要枚举到 。然后暴力更新当前因数的倍数。这样的复杂度是 ，这个复杂度大约是。

做法1

#include <bits/stdc++.h>
#include <cstring>
#define MAXN 1000003
#define MAXM 1000
#define N 1000000
const int mod = 1e9 + 7;
using namespace std;

int res[MAXN],ans[MAXN],prime[MAXN],num[MAXN],sum[MAXN],num1[MAXN];
int fac[MAXM],fac_num[MAXM],fac1[MAXM],tol1;
bool vis[MAXN];
void init()
{
    res[1] = 1;
    int cnt = 0;
    int t = 0;
    memset(vis,false,sizeof(vis));
    for(int i = 2;i <= 1000000;i++)
    {
        if(!vis[i])
        {
            prime[++cnt] = i;
            res[i] = 2;
            num[i] = 1;
            sum[i] = 1;
            num1[i] = i;
        }
        t = max(t,res[i]);
        for(int j = 1;j <= cnt;j++)
        {
            if(prime[j] > N / i)
                break;
            vis[prime[j] * i] = true;
            if(i % prime[j] == 0)
            {
                num1[prime[j] * i] = num1[i];
                res[prime[j] * i] = res[i] / (num[i] + 1) * (num[i] + 2);
                num[prime[j] * i] = num[i] + 1;
                sum[prime[j] * i] = sum[i];
                break;
            }
            else
            {
                num1[prime[j] * i] = prime[j];
                res[prime[j] * i] = res[i] * 2;
                num[prime[j] * i] = 1;
                sum[prime[j] * i] = sum[i] + 1;
            }
        }
    }
    //printf("%d\n",t);
}
int cal(int x)
{
    if(x > 64)
        return 7;
    if(x > 32)
        return 6;
    if(x > 16)
        return 5;
    if(x > 8)
        return 4;
    if(x > 4)
        return 3;
    if(x > 2)
        return 2;
    return 1;
}
void dfs(int now,int step,int n)
{
    if(step > n)
    {
        //printf("%d\n",now);
        tol1++;
        fac1[tol1] = now;
        //getchar();
        return ;
    }
    dfs(now,step + 1,n);
    for(int i = 1;i <= fac_num[step];i++)
    {
        now *= fac[step];
        dfs(now,step + 1,n);
    }
}
void test(int x)
{
        int now = x;
        int cnt = 0;
        tol1 = 0;
        while(now != 1)
        {
            fac[++cnt] = num1[now];
            fac_num[cnt] = num[now];
            while(now % fac[cnt] == 0)
                now /= fac[cnt];
        }
        printf("%d\n",tol1);
        for(int i = 1;i <= cnt;i++)
            printf("%d %d\n",fac[i],fac_num[i]);
        dfs(1,0,cnt);
        printf("%d\n",tol1);
}
int main()
{
    init();
    //printf("%d\n",res[41222]);
    int t = 0;
    //test(45360);
    //dfs(1,0,cnt);
    int tol = 0;
    for(int i = 1;i <= 1000000;i++)
    {
        bool flag = false;
        int l = max(1,(int)sqrt(i) - 200);
        int r = sqrt(i);
        if(res[i] > 80)
        {
            for(int j = r;j >= l;j--)
                if(i % j == 0)
                {
                    tol++;
                    ans[i] = j;
                    flag = true;
                    break;
                }
        }
        else
        {
            //printf("T");
            //getchar();
            flag = true;
            int now = i;
            int cnt = 0;
            tol1 = 0;
            while(now != 1)
            {
                fac[++cnt] = num1[now];
                fac_num[cnt] = num[now];
                while(now % fac[cnt] == 0)
                {
                    tol++;
                    now /= fac[cnt];
                }
            }
            dfs(1,0,cnt);
            nth_element(fac1 + 1,fac1 + tol1 / 2 + 1,fac1 + 1 + tol1);
            tol += tol1;
            ans[i] = fac1[tol1 / 2 + 1];
        }
        ans[i] = (ans[i - 1] + (i / ans[i] + ans[i]) / 2) % mod;
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans[x]);
    }
}

做法2

#include <bits/stdc++.h>
#include <cstring>
#define MAXN 1000005
typedef long long ll;
const ll MOD=1e9+7;
using namespace std;

ll f[MAXN];
ll g[MAXN];
ll T, x;

int main() {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    for (int i=1; i<=1000; ++i) {
        for (int j=1; i*j<=1000000; ++j) {
            if (j<=i) f[i*j]=max(f[i*j], (ll)j);
            else f[i*j]=max(f[i*j], (ll)i);
        }
    }
    for (int i=1; i<=1000000; ++i) {
        if (!f[i]) f[i]=1LL;
        f[i]=((ll)f[i]+(ll)i/f[i])/2LL;
        g[i]=(g[i-1]%MOD+f[i]%MOD)%MOD;
    }
    scanf("%lld", &T);
    while(T--) {
        scanf("%lld", &x);
        printf("%lld\n", g[x]);
    }
    return 0;
}