[HOJ 187][COCI 2012/2013 #1]小學老師

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

我們先來觀察f(x)有甚麼梗XD
首先，如果f(x)要大於50，x至少多少呢?
x必須被1、2、3、4、5、...、50整除!
也就是x至少要3099044504245996706400，這應該足夠應付題目範圍(10^17)了吧XD
可想而知x必須非常巨大才能讓f(x)再大一點
因此，我們可以先建表，x至少要多少，才能讓f(x)再增加一點
(以下x代表讓f(v)=y的最小v)
然後，對於一個很巨大的區間，一定有很多個數字的f(v)都是相同的
再來就是計算對於每個y，在[A,B]裡面有多少個v符合f(v)=y，然後數量乘上lolipop(y)再加起來就好了
因此，我們可以將x從大到小枚舉，數數看區間中有幾個可以被x整除且不會被更大的x整除的數字
排除被更大的x整除的數字很簡單，前面數出幾個就扣幾個就好了
為甚麼呢?
假設f(x1)=y1, f(x2)=y2，y1<y2
可以發現，x2一定可以被x1整除
然後就得證了(?)
每回詢問只要枚舉這些不超過50個的y再利用相應的x計算就可以得到答案
時間複雜度少到無法估計(?)

code:

#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<cassert>
using namespace std;
typedef long long LL;
const LL INF=9223372036854775807LL;
struct Pair
{
    LL now,p;
    Pair(){}
    Pair(const LL _now,const LL _p):now(_now),p(_p){}
    bool operator<(const Pair &p)const{return now>p.now;}
};
LL A,B;
map<LL,LL>DP;
void Initialize()
{
    priority_queue<Pair>pq;
    if(true)
    {
        bool *isp=new bool[100];
        for(int i=0;i<100;i++)isp[i]=true;
        for(int i=2;i<100;i++)if(isp[i])
        {
            pq.push(Pair(i,i));
            for(int j=2;i*j<100;j++)isp[i*j]=false;
        }
    }
    DP.clear();
    DP[1LL]=1;
    LL lcm=1LL,now=1LL;
    for(;;)
    {
        now=pq.top().now;
        while(pq.top().now<=now)
        {
            const Pair p=pq.top();pq.pop();
            if(lcm>INF/p.p)goto finished;
            lcm*=p.p;
            if(p.now<=INF/p.p)pq.push(Pair(p.now*p.p,p.p));
        }
        while(lcm%(now+1LL)==0LL)now++;
        DP[lcm]=now;
    }
    finished:;
//    for(auto it:DP)printf("(%lld,%lld)\n",it.first,it.second);
}
LL F(const LL x)
{
    if(x==2LL)return 1LL;
    auto it=DP.upper_bound(x);it--;
    while(x%(it->first)!=0LL)it--;
    return (it->second)+1LL;
}
LL Lolipop(const LL x){return x==1?0LL:Lolipop(F(x))+1;}
LL Cnt(const LL interval){return B/interval-(A-1)/interval;}
int main()
{
    Initialize();
//    for(int i=1;i<=20;i++)printf("%d=%lld\n",i,Lolipop(i));
    while(scanf("%lld%lld",&A,&B)==2)
    {
        LL used=0LL;
        LL ans=0LL;
        for(auto it=DP.rbegin();it!=DP.rend();it++)
        {
            const LL cnt=Cnt(it->first);
            ans+=(cnt-used)*(Lolipop(it->second+1LL)+1LL);
            used+=cnt-used;
        }
        assert(used==B-A+1LL);
        printf("%lld\n",ans);
    }
    return 0;
}