题解：P5946 [POI2002] B-Smooth 数

SiuuuCR7 · 2024-06-20 22:05:03 · 题解

题目解析

设 f(c,l,r,k) 表示 [l,s] 的数在分解完前 c-1 个质因子，并且第 c 个分解了 k 个后，恰好为 1 的个数（说白了，就是只有前 c 个质数中的若干个）。

那么：f(c,l,r,k)=f(c-1,l,r,k)+ f(c,\lceil\frac{l}{pc}\rceil,\lfloor \frac{r}{pc} \rfloor ,k-1)。

解释一下：

首先 k' 表示的是 \max_{l \le x \le r ,p^k}|s^{k}，这个应该很好理解。

然后第二个式子：显然我们可以把 [l,r] 内的所有满足是 p_c 的倍数的整数表示为： \lceil\frac{l}{p_c}\rceil \times p_c,( \lceil \frac{l}{p_c}\rceil +1) \times p_c...,\lfloor \frac{r}{p_c} \rfloor \times p_c，那么把所有的这些都除以一个 p_c 就可以得到上面的这个式子，然后这个东西可以用记忆化搜索去算（其实并不需要真的去使用记忆化搜索，毕竟也开不下这么大的数据）。

由于递归的层数可以代替 k ，那就可以不带 k 玩了。

可能需要一点优化，都在代码里了,请看正确代码！！！

CODE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX=1e6+10;
const int MOD=1e9+7;
inline char readchar() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
    int res = 0, f = 0;
    char ch = readchar();
    for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
    for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
    return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,m,p,sum;
int vis[MAX],cnt,pri[MAX];
inline int f(int c,int l,int r){
    if(r<=pri[c])return r-l+1;
    if(c==1){
        return __lg(r) - __lg(l - 1);
    }
    if(l==r){
        int t=l;
        for(int i=c;i>=1;i--) while(t%pri[i]==0) t/=pri[i];
        if(t==1) return 1; return 0;
    } 
    return f(c-1,l,r)+f(c,(l+pri[c]-1)/pri[c],r/pri[c]);
}
signed main(){
    n=read(),m=read(),p=read();
    vis[1]=1;
    for(int i=2;i<=p;i++){
        if(!vis[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&pri[j]*i<=p;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    cout<<f(cnt,n,n+m);
    return 0;

完结撒花，谢谢