首先我们发现要记录的东西可以搞成一个最小表示法来记录
我们只需要把这个最小的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; }