题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6588
题目大意：求(sum_{i=1}^{n}gcd(left lfloor sqrt[3]{i} ight floor,i), nleq 10^{21})
题解：考虑对(left lfloor sqrt[3]{i} ight floor)分块，将式子转换成(sum_{i=1}^{left lfloor sqrt[3]{n} ight floor}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} ight floorcdot f(n,n)+f(n,m mod n)$$
对于(f(n,n))的值，可以通过枚举(gcd)的值求和得出(f(n,n)=sum_{d|n}^{ } d cdotphi(frac{n}{d}))，线性筛预处理欧拉函数的值即可(O(nlogn))预处理所有(f(n,n))的值
对于(f(n,m))，同样可以得出，(f(n,m)=sum_{d|n}^{ } d sum_{i| frac{n}{d},ileq left lfloor frac{m}{d} ight floor}^{ }mu(i)cdotleft lfloor frac{m}{id} ight floor=sum_{d|n}^{ } phi(d)cdot left lfloor frac{m}{d} ight floor)
又由于((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+Tsqrt{n}))，这里(n)指的是(10^7)
这题的出题人原本是卡了非线性的做法，但是可以通过一定的常数优化使得(O(nlogn))的做法通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 10000001 4 #define MOD 998244353 5 int n,g[N],phi[N],p[N],cnt,res[15],flg[N]; 6 struct rua 7 { 8 int id; 9 __int128 n; 10 bool operator <(const rua &t)const{return n<t.n;} 11 }a[15]; 12 void read(__int128 &x) 13 { 14 static char ch;static bool neg; 15 for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar()); 16 for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar()); 17 x=neg?-x:x; 18 } 19 void pretype() 20 { 21 phi[1]=1; 22 for(int i=2;i<N;i++) 23 { 24 if(!flg[i])p[++cnt]=i,phi[i]=i-1; 25 for(int j=1;j<=cnt && i*p[j]<N;j++) 26 { 27 flg[i*p[j]]=1; 28 if(i%p[j]==0) 29 { 30 phi[i*p[j]]=p[j]*phi[i]; 31 break; 32 } 33 phi[i*p[j]]=(p[j]-1)*phi[i]; 34 } 35 } 36 for(int d=1;d*d<N;d++) 37 for(int n=d*d;n<N;n+=d) 38 { 39 g[n]=(g[n]+1ll*d*phi[n/d])%MOD; 40 if(d*d<n)g[n]=(g[n]+1ll*(n/d)*phi[d])%MOD; 41 } 42 } 43 inline int F(int n,__int128 M) 44 { 45 int res=(M/n)*g[n]%MOD; 46 int m=M%n; 47 if(m==0)return res; 48 for(int i=1;i*i<=n;i++) 49 { 50 int j=n/(n/i); 51 if(n%i==0) 52 { 53 res=(res+1ll*phi[i]*(m/i))%MOD; 54 if(i*i<n)res=(res+1ll*phi[n/i]*(m/(n/i)))%MOD; 55 } 56 i=j; 57 } 58 return res; 59 } 60 int main() 61 { 62 pretype(); 63 scanf("%d",&n); 64 for(int i=1;i<=n;i++) 65 read(a[i].n),a[i].id=i; 66 sort(a+1,a+n+1); 67 int ans=0,j=1; 68 __int128 i=1; 69 while(i*i*i<=a[n].n) 70 { 71 __int128 r=((i+3)*i+3)*i; 72 ans=(ans+MOD-(i*i*g[i]%MOD)+i)%MOD; 73 while(j<=n && a[j].n<r) 74 { 75 res[a[j].id]=(ans+F(i,a[j].n%i)+(a[j].n/i)*g[i])%MOD; 76 j++; 77 } 78 ans=(ans+((i+3)*i+3)*g[i])%MOD; 79 while(j<=n && a[j].n==r) 80 res[a[j++].id]=ans; 81 i++; 82 } 83 for(int i=1;i<=n;i++) 84 printf("%d ",res[i]); 85 }