[2019HDU多校第一场][HDU 6588][K. Function]

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6588

题目大意：求$\sum_{i=1}^{n}gcd(\left \lfloor \sqrt[3]{i} \right \rfloor,i),\ n\leq 10^{21}$

题解：考虑对$\left \lfloor \sqrt[3]{i} \right \rfloor$分块，将式子转换成$\sum_{i=1}^{\left \lfloor \sqrt[3]{n} \right \rfloor}\sum_{j=i^3}^{(i+1)^3-1}gcd(i,j)$

　　　考虑函数$f(n,m)=\sum_{i=1}^{m}gcd(n,i)$，由于$gcd(x,y)=gcd(x\ mod\ y,y)$，可以得出$$f(n,m)=\sum_{i=1}^{m}gcd(n,i)=\left \lfloor \frac{m}{n} \right \rfloor\cdot f(n,n)+f(n,m\ mod\ n)$$

　　　对于$f(n,n)$的值，可以通过枚举$gcd$的值求和得出$f(n,n)=\sum_{d|n}^{ } d \cdot\phi(\frac{n}{d})$，线性筛预处理欧拉函数的值即可$O(nlogn)$预处理所有$f(n,n)$的值

　　　对于$f(n,m)$，同样可以得出，$f(n,m)=\sum_{d|n}^{ } d \sum_{i| \frac{n}{d},i\leq \left \lfloor \frac{m}{d} \right \rfloor}^{ }\mu(i)\cdot\left \lfloor \frac{m}{id} \right \rfloor=\sum_{d|n}^{ } \phi(d)\cdot \left \lfloor \frac{m}{d} \right \rfloor$

　　　又由于$(i+1)^3-1=i^3+3i^2+3i$是$i$的倍数，所以对于每个循环中的$i$，有$$\sum_{j=i^3}^{(i+1)^3-1}gcd(i,j)=f(i,i^3+3i^2+3i)-f(i,i^3)+gcd(i,i^3)=(3i+3)\cdot f(i,i)+i$$

　　　因此对于每个询问，最多只需要求一次$f(n,m)$就好（即最后的$i$），而求一次$f(n,m)$的时间复杂度为$O(\sqrt{n})$，所以每次询问的复杂度是$O(n+\sqrt{n})$。又因为有多组询问，可以考虑通过离线处理将总的时间复杂度降为$O(nlogn+T\sqrt{n})$，这里$n$指的是$10^7$

　　　这题的出题人原本是卡了非线性的做法，但是可以通过一定的常数优化使得$O(nlogn)$的做法通过

 #include<bits/stdc++.h>

 using namespace std;

 #define N 10000001

 #define MOD 998244353

 int n,g[N],phi[N],p[N],cnt,res[],flg[N];

 struct rua

 {

     int id;

     __int128 n;

     bool operator <(const rua &t)const{return n<t.n;}

 }a[];

 void read(__int128 &x)

 {

     static char ch;static bool neg;

     for(ch=neg=;ch<'' || ''<ch;neg|=ch=='-',ch=getchar());

     for(x=;''<=ch && ch<='';(x*=)+=ch-'',ch=getchar());

     x=neg?-x:x;

 }

 void pretype()

 {

     phi[]=;

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

       {

       if(!flg[i])p[++cnt]=i,phi[i]=i-;

       for(int j=;j<=cnt && i*p[j]<N;j++)

         {

         flg[i*p[j]]=;

         if(i%p[j]==)

           {

           phi[i*p[j]]=p[j]*phi[i];

           break;

           }

         phi[i*p[j]]=(p[j]-)*phi[i];

         }

       }

     for(int d=;d*d<N;d++)

       for(int n=d*d;n<N;n+=d)

         {

         g[n]=(g[n]+1ll*d*phi[n/d])%MOD;

         if(d*d<n)g[n]=(g[n]+1ll*(n/d)*phi[d])%MOD;

         }

 }

 inline int F(int n,__int128 M)

 {

     int res=(M/n)*g[n]%MOD;

     int m=M%n;

     if(m==)return res;

     for(int i=;i*i<=n;i++)

       {

       int j=n/(n/i);

       if(n%i==)

         {

         res=(res+1ll*phi[i]*(m/i))%MOD;

         if(i*i<n)res=(res+1ll*phi[n/i]*(m/(n/i)))%MOD;

         }

       i=j;

       }

     return res;

 }

 int main()

 {

     pretype();

     scanf("%d",&n);

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

       read(a[i].n),a[i].id=i;

     sort(a+,a+n+);

     int ans=,j=;

     __int128 i=;

     while(i*i*i<=a[n].n)

       {

       __int128 r=((i+)*i+)*i;

       ans=(ans+MOD-(i*i*g[i]%MOD)+i)%MOD;

       while(j<=n && a[j].n<r)

         {

         res[a[j].id]=(ans+F(i,a[j].n%i)+(a[j].n/i)*g[i])%MOD;

         j++;

         }

       ans=(ans+((i+)*i+)*g[i])%MOD;

       while(j<=n && a[j].n==r)

         res[a[j++].id]=ans;

       i++;

       }

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

       printf("%d\n",res[i]);

 }

巴特西

[2019HDU多校第一场][HDU 6588][K. Function]

最新文章

热门文章