P7586题解

Alarm5854 · 2021-05-06 14:40:03 · 题解

这道题目一看数据范围就知道它是一道数学题，不过要怎样处理呢？

令 f(x) 为不能整除 x 的最小整数，其中 x\ge 3，很显然的是 \text{strength}(x)=\text{strength}(f(x))+1，这根据定义可知。

关键就在这里：对于所有 x\in [3,10^{17}]，一定有 f(x)\le 41，因为 \text{lcm}(1,2,...,40)<10^{17}，而 \text{lcm}(1,2,...,41)>10^{17}，所以只需要预处理一下 3 到 41 之间的 \text{strength}(i) 即可。

预处理完之后，计算 3 到 n 的 \text{strength}(i) 的和。答案初始化为 2n+k，其中 k 为任意常数，因为之后计算答案的时候可以抵消，枚举 2 到 40，并更新 \text{lcm}，再更新答案即可。

#include<ctime>
#include<cstdio>
#include<cctype>
#define ll long long
using namespace std;
ll read(){
    char c;
    ll x=0,f=1;
    while(!isdigit(c=getchar()))
        f-=2*(c=='-');
    while(isdigit(c)){
        x=x*10+f*(c-48);
        c=getchar();
    }
    return x;
}
ll gcd(ll x,ll y){
    while(x&&y){
        ll z=x;
        x=y;
        y=z%y;
    }
    return x|y;
}
ll lcm(ll x,ll y){
    return x/gcd(x,y)*y;
}
ll a,b,str[55];
ll f(ll x){//找最小的正整数使得不能整除x
    ll t=2;
    for(;;++t){
        if(x%t)
            break;
    }
    return t;
}
ll work(ll x){
    ll tmp=1;
    ll res=x*2;
    for(ll i=2;i<43;++i){
        tmp=lcm(tmp,i);
        res+=x/tmp*(str[i+1]-str[i]);//在1~x中f(i)>tmp的有x/tmp个，而这些开始默认它为tmp，所以要改变
    }
    return res;
}
int main(){
    a=read()-1;
    b=read();
    for(ll i=3;i<=43;++i)
        str[i]=str[f(i)]+1;//预处理strength(i)，实际上并不需要确切值，像这里其实处理的是strength(i)-1
    printf("%lld",work(b)-work(a));
    return 0;
}