自动搬运

查看原文

来自洛谷，原作者为

	Caro23333 Dream Theater 脑残粉

搬运于2025-08-24 22:07:42，当前版本为作者最后更新于2019-08-08 23:32:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路与Great_Influence相似，更加详细且有代码。

首先观察题目条件。若$t$是最小不整除$x$的正整数,则有：

• 对于任意$i(1\le i<t)$都有$i\mid x$，即$lcm(1,2,\dots,t-1)\mid x$
• $lcm(1,2,\dots,t)\nmid x$

根据这个原理我们进行打表不难发现使得$lcm(1,2,\dots,t)\le 10^{18}$的最大的$t$是$42$，从而对于$3\le x\le 10^{18}$的$x$，$2\le t\le 42$.

将$1$到$42$每一个位置的前缀$lcm$求出，并且考虑以$i(2\le i\le 42)$为转移点的$x(43\le x\le n)$的数量。注意到$lcm(1,2,\dots,i-1)\mid lcm(1,2,\dots,i)$，所以满足上述两个条件的$x$的数量就是$[43,n]$上$lcm(1,2,\dots,i-1)$的倍数的数量减去$lcm(1,2,\dots,i)$的倍数的数量。

注意到这些$x$都满足$f[x] = f[i]+1$，在预处理$f[2],f[3],\dots,f[42]$之后可以计算出对于每个$k(1\le k\le 5)$共有几个$x$满足$f[x] = k$，从而可以轻易地得到答案。

时间复杂度显然是正确的。

代码：

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define mod 1000000007

using namespace std;
typedef long long ll;
const int MAXN = 50;
int f[MAXN];
ll n,lcm[MAXN],cnt[10];
inline ll gcd(ll a, ll b)
{
    return b?gcd(b,a%b):a;
}
inline ll calc(ll l, ll r, ll x)
{
    return r/x-(l-1)/x; 
}
inline ll qpow(ll a, ll b)
{
    ll res = 1;
    for(; b; a = a*a%mod, b >>= 1ll)
        if(b&1ll)
            res = res*a%mod;
    return res;
}

int main()
{
    cin >> n;
    f[2] = 1;
    for(int i = 3; i<=50; i++)
        for(int j = 2; j<i; j++)
            if(i%j)
            {
                f[i] = f[j]+1;
                break;
            }
    lcm[1] = 1;
    int pos = 2;
    for(pos = 2; pos<=50; pos++)
  	{
        lcm[pos] = lcm[pos-1]*(pos/gcd(pos,lcm[pos-1]));
        if(lcm[pos]>n)
            break;
    }
    for(int i = 2; i<=pos; i++)
        cnt[f[i]+1] += calc(pos+1,n,lcm[i-1])-calc(pos+1,n,lcm[i]);
    for(int i = 2; i<=pos; i++)
        cnt[f[i]]++;
    ll ans = 1;
    for(int i = 2; i<=5; i++)
        ans = ans*qpow(i,cnt[i])%mod;
    cout << ans << endl;
    return 0;
}