CF261E Maxim and Calculator

题目描述

Maxim has got a calculator. The calculator has two integer cells. Initially, the first cell contains number 11 , and the second cell contains number 00 . In one move you can perform one of the following operations:

Let's assume that at the current time the first cell contains number aa , and the second cell contains number bb . Write to the second cell number b+1b+1 ;
Let's assume that at the current time the first cell contains number aa , and the second cell contains number bb . Write to the first cell number a·ba⋅b .

Maxim is wondering, how many integers xx (l<=x<=r)(l<=x<=r) are there, such that we can write the number xx to the first cell of the calculator, having performed at most pp moves.

输入格式

The first line contains three integers: ll , rr , pp (2<=l<=r<=10^{9},1<=p<=100)(2<=l<=r<=109,1<=p<=100) .

The numbers in the line are separated by single spaces.

输出格式

In a single line print a single integer — the answer to the problem.

题意翻译

二元组(a,b)(a,b),可以变成(a,b+1)(a,b+1)或(ab,b)(a**b,b)
你有初始二元组(1,0)(1,0),给你区间[l,r][l,r],和一个整数pp,在区间内选一个数xx,使(1,0)(1,0)在不超过pp步变化后,第一维的值变成xx,求xx的个数

Translated by @Fheiwn

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

输入 #3复制

输出 #3复制

题解：

这是2019.10.16模拟赛的一道题。

一开始我发现，如果每次操作都加的话，那么操作数对应的答案都是可行的（这很显然）。但是这样肯定不会是答案，所以我们应该继续考虑一种情况：操作二，乘法运算。

然后我想到了整数的唯一分解定理：一个正整数可以被唯一分解成若干个质数的乘积。

这个思路紧紧地抓住了我的心//那么，对于一个数，我们肯定可以用算术基本定理把它分成若干个数的乘积，那么，如果这些数最大的那个和这些数的个数的和（最大的数+数的个数）比(p)小，那么这个数就是合法的。

证明是显然的：我们操作的过程是从1累加，每逢到了要作为(a)的质因子的数，就多用一次操作乘过去，这样，一直到了最后的质因子（也是最大的），就能乘出(a)。

这样就确定了我们的判定思路。但是如果暴力枚举的话，TLE是没跑的。

所以，我们进一步开始细细地琢磨怎么降低复杂度。

通过刚刚的讲解，我们发现，如果有一个数被唯一分解成若干个质数的乘积，并且其最大的质因子要比(p)还要大，那么这个数就根本不可能合法。

所以，我们发现，(ble p)是必须的。所以，我们就可以通过线性筛选处理出(le p)的所有质数，并且通过深搜来处理出所有能用这些质数表示出来（乘出来）的数。

这里简单说一下为什么要用深搜：根据算术基本定理，我们会有很多质数来乘成一个合数。而且，这些质数是可以重复的：也就是说，普通的循环遍历根本不会满足这样的要求，所以需要通过递归求解（即深搜）。

以上都是预处理部分，现在我们要检验这些数是否能在$le p $的次数内出解。

~~（到这个地方本蒟蒻就不会了。模拟赛40分*￥%）~~

这个地方要用(DP)求解......

设(f[i] [j])表示把第一元变成(i)，第二元变成(j)所用的操作二的最少次数。为什么这么设置呢？因为操作一作为加法，是可以直接计算出来的。而且，因为这样设置转移方程一定会导致爆空间，第二维（表示第二元）一定是要被滚动掉的。

所以，我们对深搜处理出的数列进行排序。外层枚举(2-p)，内层枚举(1-tot)（(tot)表示数列的长度），如果(i|a[j])，则用单调队列指针寻找(i imes a[k]=a[j])，这时就用(dp[k])更新(dp[j])，判断其加上数的个数（(i)）是否超过了(p)。

代码如下：（注意空间范围，不然会死得超级惨）

#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int maxp=3*1e6+1;
int l,r,p,ans;
bool v[maxp],vis[maxp];
int a[maxp],prime[maxp],dp[maxp],tot,cnt;
void euler(int n)
{
    cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
            prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(i*prime[j]>=p)
                break;
            v[i*prime[j]]=1;
            if(i%prime[j]==0)
                break;
        }
    }
}
void scan(int x,int step)
{
    a[++tot]=x;
    for(int i=step;i<=cnt;i++)
    {
        if(prime[i]*(ll)x<=r)
            scan(prime[i]*x,i);
        else
            return;
    }
}
int main()
{
    scanf("%d%d%d",&l,&r,&p);
    euler(p-1);
    scan(1,1);
    sort(a+1,a+tot+1);
    memset(dp,0x3f,sizeof(dp)); 
    dp[1]=0;
    for(int i=2;i<=p;i++) 
    {
        int k=1;
        for(int j=1;j<=tot;j++) 
            if(a[j]%i==0)
            {
                while(a[k]*i<a[j]) 
                    k++;
                dp[j]=min(dp[j],dp[k]+1);
                if(dp[j]+i<=p) 
                    vis[j]=1;
            }
    }
    for(int i=1;i<=tot;i++) 
        if(vis[i] && a[i]>=l) 
            ans++;
    printf("%d",ans);
    return 0;
}