[HOJ 187] 小學老師

作法：

首先觀察有哪些數字的$f$值會變成$i$，會發現這就等價於這個數是$1,...,i-1$的倍數，但不是$i$的倍數。因此可以想像$10^{17}$範圍內的數字的$f$值都不會太大，因為$1,...,n$的最小公倍數成長的速度非常快。可以預處理出最大的$f$值只會到$41$，因此對於所求的值，對於每一項$L(i)$來說，可以先把他換成$L(f(i))+1$，這樣就只需要知道$[A,B]$之間有幾個數的$f$值等於$i$了（$i=1,...,41$），而這顯然用前面的等價條件就可以算了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
inline LL cal(LL a,LL b)
{
    return a/b ;
}
int f[50],lo[50] ;
LL lcm[50] ;
main()
{
    lcm[1]=1 ; lcm[2]=2 ;
    f[2]=1 ; lo[2]=1 ;
    for(int i=3;i<=41;i++)
    {
        lcm[i]=lcm[i-1]/__gcd(lcm[i-1],(LL)i)*i ;
        for(int j=2;;j++) if(i%j)
            {f[i]=j ; break ;}
        lo[i]=lo[f[i]]+1 ;
    }
    LL a,b ;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        LL ans=0 ;
        for(int i=2;i<=41;i++)
        {
            LL num=cal(b,lcm[i-1])-cal(b,lcm[i]) ;
            num-=cal(a-1,lcm[i-1])-cal(a-1,lcm[i]) ;
            ans+=num*lo[i] ;
        }
        printf("%lld\n",ans+b-a+1) ;
    }
}