[问题解决] LOGU P5946 [POI2002] B 平滑编号
最编程
2024-04-30 14:32:09
...
感觉这题还是挺神的。
设 \(f(c,l,r,k)\) 表示 \([l,r]\) 的数在分解完前 \(c-1\) 个质因子,并且第 \(c\) 个分解了 \(k\)个后,恰好为 \(1\) 的个数(说白了,就是只有前 \(c\) 个质数中的若干个)。
那么:\(f(c,l,r,k)=f(c-1,l,r,k)+f(c,\lceil \frac {l}{p_c} \rceil,\lfloor \frac{r}{p_c} \rfloor,k-1)\)
解释一下:
首先 \(k'\) 表示的是 \(\max_{l\le x \le r,p^k| x}\{k\}\),这个应该很好理解。
然后第二个式子:显然我们可以把 \([l,r]\) 内的所有满足是 \(p_c\) 的倍数的整数表示为:\(\lceil \frac {l}{p_c} \rceil \times p_c,(\lceil \frac {l}{p_c} \rceil+1)\times p_c \dots ,\lfloor \frac{r}{p_c} \rfloor \times p_c\),那么把所有的这些都除以一个 \(p_c\) 就得到了上面的式子,然后这个东西可以用类似记忆化搜索的东西去算(其实并不需要真的记忆化,毕竟也开不下这么大的数组)。
由于递归的层数可以带替 \(k\),那就可以不带 \(k\) 玩了。
可能需要一点优化,都在代码里了:
#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 (int)(log(r)/log(2.0)+1.0+1e-6)-(int)(log(l-1)/log(2.0)+1.0+1e-6);
}
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;
}
}
// for(int i=1;i<=cnt;i++) cout<<pri[i]<<" ";
cout<<f(cnt,n,n+m);
return 0;
}
原文地址:https://www.cnblogs.com/wapmhac0523/p/16370120.html