洛谷 P3455 [POI2007]ZAP-Queries || 洛谷P2522,bzoj2301

https://www.luogu.org/problemnew/show/P3455

就是https://www.cnblogs.com/hehe54321/p/9315244.html里面的方法2了，升级版的整除分块，可以两个变量一起搞

预处理莫比乌斯函数的前缀和之后就可以每次$O(\sqrt{n}+\sqrt{m})$回答

那篇题解里面用了一个技巧：${\lfloor}\frac{{\lfloor}\frac{a}{b}{\rfloor}}{c}{\rfloor}={\lfloor}\frac{a}{bc}{\rfloor}$

（当然a,b,c都为正整数）

证了好久。。。

这么证：

设${\lfloor}\frac{a}{bc}{\rfloor}=p$，则p为整数，且$p<=\frac{a}{bc}<p+1$

则$pc<=\frac{a}{b}<pc+c$

而$pc$与$pc+c$都为整数

因此$pc<={\lfloor}\frac{a}{b}{\rfloor}<pc+c$

所以$p<=\frac{{\lfloor}\frac{a}{b}{\rfloor}}{c}<p+1$

所以${\lfloor}\frac{{\lfloor}\frac{a}{b}{\rfloor}}{c}{\rfloor}=p={\lfloor}\frac{a}{bc}{\rfloor}$

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define N 50100

 ll prime[N+],len,mu[N+],dd[N+];

 bool nprime[N+];

 ll a,c,n,m,k,ans,ed;

 int main()

 {

     ll i,j,T,TT;

     mu[]=;

     for(i=;i<=N;i++)

     {

         if(!nprime[i])    prime[++len]=i,mu[i]=-;

         for(j=;j<=len&&i*prime[j]<=N;j++)

         {

             nprime[i*prime[j]]=;

             if(i%prime[j]==)    {mu[i*prime[j]]=;break;}

             else    mu[i*prime[j]]=-mu[i];

         }

     }

     for(i=;i<=N;i++)    dd[i]=dd[i-]+mu[i];

     scanf("%lld",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%lld%lld%lld",&n,&m,&k);n/=k;m/=k;

         ans=;

         if(n>m)    swap(n,m);

         for(i=;i<=n;i=j+)

         {

             j=min(n,min(n/(n/i),m/(m/i)));

             ans+=(dd[j]-dd[i-])*(n/i)*(m/i);

         }

         printf("%lld\n",ans);

     }

     return ;

 }

https://www.luogu.org/problemnew/show/P2522

https://www.lydsy.com/JudgeOnline/problem.php?id=2301

这题基本一样的，就是加个容斥。。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define N 50100

 ll prime[N+],len,mu[N+],dd[N+];

 bool nprime[N+];

 ll a,c,n,m,k;

 ll calc(ll n,ll m)

 {

     if(n==||m==)    return ;

     ll ans=;

     if(n>m)    swap(n,m);

     n/=k;m/=k;

     for(ll i=,j;i<=n;i=j+)

     {

         j=min(n,min(n/(n/i),m/(m/i)));

         ans+=(dd[j]-dd[i-])*(n/i)*(m/i);

     }

     return ans;

 }

 int main()

 {

     ll i,j,T,TT;

     mu[]=;

     for(i=;i<=N;i++)

     {

         if(!nprime[i])    prime[++len]=i,mu[i]=-;

         for(j=;j<=len&&i*prime[j]<=N;j++)

         {

             nprime[i*prime[j]]=;

             if(i%prime[j]==)    {mu[i*prime[j]]=;break;}

             else    mu[i*prime[j]]=-mu[i];

         }

     }

     for(i=;i<=N;i++)    dd[i]=dd[i-]+mu[i];

     scanf("%lld",&T);

     for(TT=;TT<=T;TT++)

     {

         scanf("%lld%lld%lld%lld%lld",&a,&n,&c,&m,&k);

         printf("%lld\n",calc(n,m)-calc(a-,m)-calc(n,c-)+calc(a-,c-));

     }

     return ;

 }

巴特西

洛谷 P3455 [POI2007]ZAP-Queries || 洛谷P2522,bzoj2301

最新文章

热门文章