题解 P5153 【简单的函数】

· · 题解

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

首先观察题目条件。若t是最小不整除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;
}