每日一题 CF83D Numbers 题解

首先我们发现要记录的东西可以搞成一个最小表示法来记录
我们只需要把这个最小的k作为表示方案就可以了
然后具体的我们每次求这个答案需要递归容斥下去
首先要是能被k整除的，其次我们把小于k的方案减去即可
具体我们写个calc函数然后不断递归就可以了！
细节是我们要判断一下不是质数的情况直接return 0
我们可以先筛除小于1e6的质数，剩下的暴力判断，再加上记忆化，总复杂度O(能过)
代码：

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ------------------------------------------------ "<<endl
#define LL long long
#define DB double
#define mpt make_pair
#define pb push_back
inline int read(){
    int nm=0; bool fh=true; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return fh?nm:-nm;
}
#define M 1000200
#define MAXN 1000000
int pri[M],cnt; bool np[M];
unordered_map<int,int>Hv;
inline bool check(int x){
    if(x<=MAXN) return np[x]^1;
    if(Hv[x]) return Hv[x]>0;
    for(int i=2;i*i<=x;i++) if(x%i==0){
        Hv[x]=-1; return false;
    } Hv[x]=1; return true;
}
inline int gt(int x,int k){
    if(!check(k)) return 0;
    int all=x/k,R=min(k-1,x/k);
    for(int i=2;i<=R;i++) all-=gt(x/k,i);
    return all;
}

int main(){
    for(int i=2;i<=MAXN;i++){
        if(!np[i]) pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<=MAXN;j++){
            np[i*pri[j]]=true;
            if(i%pri[j]==0) break;
        }
    }
    int l=read(),r=read(),K=read();
    printf("%d\n",gt(r,K)-gt(l-1,K));
    return 0;
}