[luogu5438]记忆

令$f(x)=\frac{x}{\max_{k^{2}|x}k^{2}}$，最优解即将$f(l),f(l+1),...,f(r)$排序，那么每存在一种不同的数则答案减1，那么$x$出现当且仅当$f(x)=x$且存在$k$满足$l\le xk^{2}\le r$

枚举$k$，那么即求$(\lfloor\frac{l-1}{k^{2}}\rfloor,\lfloor\frac{r}{k^{2}}\rfloor]$中有多少个数最大平方因子为1，但同时还有重复，即区间右端点要对上一次左端点取min，之后拆成两个前缀和，即求$[1,n]$中$f(x)=x$的数个数

类似洛谷4318，容斥即$\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^{2}}\rfloor$，再对$i$数论分块，对于$i\le n^{\frac{1}{3}}$，共$o(n^{\frac{1}{3}})$种；对于$i>n^{\frac{1}{3}}$，则有$\frac{n}{i^{2}}\le n^{\frac{1}{3}}$，同样共$o(n^{\frac{1}{3}})$种

再对外层$k$数论分块，对于较小的一部分直接线性筛求出$\mu$，对于较大的部分套用上面的做法，考虑复杂度：对于$k\le r^{x}$，复杂度为$r^{\frac{1}{3}}\int_{0}^{r^{x}}k^{-\frac{2}{3}}\ dk=o(r^{\frac{x+1}{3}})$；对于$k>r^{x}$，则有$\frac{r}{k^{2}}\le r^{1-2x}$，复杂度为$o(r^{1-2x})$

取$\frac{x+1}{3}=1-2x$，解得$x=\frac{2}{7}$，总复杂度为$o(r^\frac{3}{7})$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 10000005

 4 #define ll long long

 5 int p[N],vis[N],mu[N],s1[N],s2[N];

 6 ll l,r,ans;

 7 ll calc(ll n){

 8     if (n<N-4)return s2[n];

 9     ll ans=0;

10     for(ll i=1,j;i*i<=n;i=j+1){

11         j=(ll)sqrt(n/(n/(i*i)));

12         ans+=n/(i*i)*(s1[j]-s1[i-1]);

13     }

14     return ans;

15 }

16 int main(){

17     mu[1]=1;

18     for(int i=2;i<N-4;i++){

19         if (!vis[i]){

20             p[++p[0]]=i;

21             mu[i]=-1;

22         }

23         for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){

24             vis[i*p[j]]=1;

25             if (i%p[j])mu[i*p[j]]=mu[i]*mu[p[j]];

26             else{

27                 mu[i*p[j]]=0;

28                 break;

29             }

30         }

31     }

32     for(int i=1;i<N-4;i++){

33         s1[i]=s1[i-1]+mu[i];

34         s2[i]=s2[i-1]+mu[i]*mu[i];

35     }

36     scanf("%lld%lld",&l,&r);

37     l--;

38     ans=r-l;

39     ll las=r;

40     for(ll i=1,j;i*i<=r;i=j+1){

41         if (i*i>l)j=(ll)sqrt(r/(r/(i*i)));

42         else j=(ll)sqrt(min(l/(l/(i*i)),r/(r/(i*i))));

43         ans-=calc(min(r/(i*i),las))-calc(l/(i*i));

44         las=l/(i*i);

45     }

46     printf("%lld",ans);

47 }

巴特西

[luogu5438]记忆

最新文章

热门文章