洛谷 P3327 [SDOI2015]约数个数和 || Number Challenge Codeforces

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

不会做。

去搜题解...为什么题解都用了一个奇怪的公式？太奇怪了啊。。。

公式是这样的：

$d(xy)=\sum_{i|x}\sum_{j|y}[(i,j)=1]$

证明：（转自：https://23613.blog.luogu.org/solution-p3327）

考虑一个质因子p，设x中p的指数为a，y中p的指数为b（指质因数分解结果中指数），那么根据因数个数定理，这个质因子对式子左边的贡献（指使得答案乘上的值）是a+b+1；在式子右边，要么i中p的指数为0且j中p的指数为1~b，要么j中p的指数为0且i中p的指数为1~a，要么i和j中p的指数均为0（为了保证i,j互质），所以p的贡献是(b+a+1)。那么左右两边就相等了...

没办法了，背公式吧...找不到别的做法

答案要求的式子ans可以化为$\sum_{i=1}^n\sum_{j=1}^m[(i,j)=1]{\lfloor}\frac{n}{i}{\rfloor}{\lfloor}\frac{m}{j}{\rfloor}$

反演一下，得到$ans=\sum_{k=1}^m\mu(k)\sum_{i=1}^{{\lfloor}\frac{n}{k}{\rfloor}}\sum_{j=1}^{{\lfloor}\frac{m}{k}{\rfloor}}{\lfloor}\frac{n}{ik}{\rfloor}{\lfloor}\frac{m}{jk}{\rfloor}$（不妨设n<=m）

设$f(x)=\sum_{i=1}^x{\lfloor}\frac{x}{i}{\rfloor}$，这个显然可以n*sqrt预处理出来

$ans=\sum_{k=1}^m\mu(k)f({\lfloor}\frac{n}{k}{\rfloor})f({\lfloor}\frac{m}{k}{\rfloor})$

那么原式也可以简单的在一次询问sqrt的时间内求出

本以为就这样子A掉了，结果...T飞了

不管了。。O3开开A掉

网上找了一下，有一个方法卡常数：可以发现f函数是约数个数函数的前缀和，因此可以筛出约数个数然后直接前缀和，这样预处理就是O(n)的

 #pragma GCC optimize(3)

 #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;

 ll prime[],len,ff[],mu[];

 bool nprime[];

 ll ans,n,m;

 int main()

 {

     ll i,j,k,T;

     mu[]=;

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

     {

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

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

         {

             nprime[i*prime[j]]=;

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

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

         }

     }

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

     for(k=;k<=;k++)

     {

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

         {

             j=min(k,k/(k/i));

             ff[k]+=(j-i+)*(k/i);

         }

     }

     //for(i=1;i<=10;i++)    printf("%lld\n",ff[i]);

     scanf("%lld",&T);

     while(T--)

     {

         scanf("%lld%lld",&n,&m);

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

         ans=;

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

         {

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

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

         }

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

     }

     return ;

 }

http://codeforces.com/contest/235/problem/E

是不是感觉非常像？

事实上，不仅式子像，结论也是一样的。。。好神奇啊

结论是：$d(xyz)=\sum_{i|x}\sum_{j|y}\sum_{k|z}[(i,j)=1][(j,k)=1][(i,k)=1]$

证明也是类似的；貌似可以推广到更高维(?没试过)

同样的，$ans=\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c[(i,j)=1][(j,k)=1][(i,k)=1]{\lfloor}\frac{a}{i}{\rfloor}{\lfloor}\frac{b}{j}{\rfloor}{\lfloor}\frac{c}{k}{\rfloor}$

耶，我又不会了，反演嘛式子推不清楚，乱搞嘛搞不出来

到网上找，发现一个技巧：如果只是要求XXX=1，用$\sum_{d|k}\mu(d)=[k=1]$去代比直接反演更方便

有了这样一个做法：

枚举i，搞出所有可能的j,k（指与i互质且在范围内），分别放入数组aj,ak

那么就需要从aj,ak内分别取一个元素x,y，如果(x,y)==1则可以计算贡献

也就是要计算$\sum_{j{\in}aj}\sum_{k{\in}ak}[(j,k)=1]{\lfloor}\frac{b}{j}{\rfloor}{\lfloor}\frac{c}{k}{\rfloor}=\sum_{j{\in}aj}\sum_{k{\in}ak}\sum_{d|(j,k)}\mu(d){\lfloor}\frac{b}{j}{\rfloor}{\lfloor}\frac{c}{k}{\rfloor}$

考虑对每一个d统计贡献，复杂度n^2*log

 #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;

 int prime[],len,mu[];

 bool nprime[];

 int a,b,c,mm;

 unsigned ans,a1,n1,n2;

 bool aj[],ak[];

 int main()

 {

     int i,j,k,d;

     mu[]=;

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

     {

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

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

         {

             nprime[i*prime[j]]=;

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

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

         }

     }

     scanf("%d%d%d",&a,&b,&c);

     mm=max({a,b,c});

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

     {

         a1=;

         for(j=;j<=b;j++)

             aj[j]=(__gcd(i,j)==);

         for(k=;k<=c;k++)

             ak[k]=(__gcd(i,k)==);

         for(d=;d<=mm;d++)

         {

             n1=n2=;

             for(j=d;j<=b;j+=d)

                 n1+=aj[j]*(b/j);

             for(k=d;k<=c;k+=d)

                 n2+=ak[k]*(c/k);

             a1+=n1*n2*mu[d];

         }

         ans+=a1*(a/i);

     }

     printf("%u",ans%);

     return ;

 }

巴特西

洛谷 P3327 [SDOI2015]约数个数和 || Number Challenge Codeforces - 235E

最新文章

热门文章