• 欢迎光临~

CF261E 翻

开发技术 开发技术 2022-12-11 次浏览

[[DP]] [[two pointers]]
link
A hint: There is near 3000000 numbers with maximal prime divisor <=100.

According to the hint, we can list all the passible numbers.
Then what we need to do is judge whether the number meets the condition or not.

We must make the cost smaller, so we can't simply mark all the prime divisors of each number.

We need to combine several divisors.
And, the maximal prime divisors must be selected (a conclusion).

We can do DP, by two pointers, in the sorted list.

#include<bits/stdc++.h>
using namespace std;
const int N=3000006;
int a[N],f[N],b[N],l,r,n,m,ans;
int main(){
	int i,j;
	scanf("%d%d%d",&l,&r,&n);
	a[m++]=1;
	for(i=2;i<=n;i++){
		for(j=2;j<i;j++)if(i%j==0)goto E;
		for(j=0;j<m;j++)if(1ll*a[j]*i<=r)a[m++]=a[j]*i;
		E:;
	}
	sort(a,a+m);
	memset(f,0x7f,sizeof(f));f[0]=0;
	//DP and two_pointers 
	for(int i=2;i<n;i++)
	for(int j=0,k=0;j<m;j++)
	if(a[j]%i==0){
		if(f[k]+1<f[j]){
			f[j]=f[k]+1;
			if(f[j]+i<=n)b[j]=1;
		}
		k++;
	}
	for(int i=0;i<m;i++)if(a[i]>=l&&b[i])ans++;
	printf("%d",ans);
}
程序员灯塔
转载请注明原文链接:CF261E 翻
喜欢 (0)