Philips and Calculator

代码

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 3 * 1e6;

int l , r , p , tp , prime[105] , num[N + 5] , n , vis[105] , f[N + 5] , ok[N + 5] , ans;

inline void getp()

{

	vis[1] = vis[0] = 1;

	for(register int i = 2; i <= p; i++)

	{

		if (!vis[i]) prime[++tp] = i;

		for(register int j = 1; j <= tp && prime[j] * i <= p; j++)

		{

			vis[i * prime[j]] = 1;

			if (i % prime[j] == 0) break;

		}

	}

}

inline void dfs(int x , int v)

{

	num[++n] = v;

	for(register int i = x; i <= tp; i++)

	if (prime[i] * (long long)v <= r) dfs(i , prime[i] * v);

}

int main()

{

	scanf("%d%d%d" , &l , &r , &p);

	getp();

	dfs(1 , 1);

	num[++n] = 1;

	sort(num + 1 , num + n + 1);

	f[1] = 0;

	for(register int i = 2; i <= n; i++) f[i] = 1e9;

	for(register int i = 2; i <= p; i++)

	{

		register int j = 1;

		for(register int k = 1; k <= n; k++)

		{

			while (j <= n && num[k] * i != num[j]) j++;

			if (j > n) break;

			if (f[k] + 1 < f[j]) f[j] = f[k] + 1;

			if (f[j] + i <= p && num[j] >= l && !ok[j]) ok[j] = 1 , ans++;

		}

	}

	printf("%d" , ans);
巴特西

Philips and Calculator

代码

最新文章

热门文章
