题目大意：
定义函数$f(m)=displaystylesum_{a=0}^{m-1}sum_{b=0}^{m-1}[m
mid ab]$，$g(n)=displaystylesum_{mmid n}f(m)$。
共有$q(qleq2 imes10^4)$次询问，每次询问$g(n)(nleq10^9)$的值。
思路：
对$n$分解质因数，得$n=displaystyleprod_{i=1}^rp_i^{q_i}$。
推公式得$g(n)=displaystyleprod_{i=1}^rfrac{(p_i^{q_i+1})-1}{p_i^2-1}-nprod_{i=1}^r(q_i+1)$。
先预处理出质数表，然后暴力分解质因数即可。
1 #include<cstdio> 2 #include<cctype> 3 typedef unsigned long long qword; 4 typedef unsigned __int128 oword; 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 const int M=31628,SIZE=3403; 13 bool b[M]; 14 int p[SIZE]; 15 inline void init() { 16 for(register int i=2;i<M;i++) { 17 if(!b[i]) { 18 p[++p[0]]=i; 19 for(register int j=i*2;j<M;j+=i) { 20 b[j]=true; 21 } 22 } 23 } 24 } 25 int main() { 26 init(); 27 const int T=getint(); 28 for(register int t=1;t<=T;t++) { 29 int n=getint(); 30 qword prod1=1,prod2=n; 31 for(register int i=1;p[i]*p[i]<=n;i++) { 32 if(n%p[i]!=0) continue; 33 int q=0; 34 qword tmp=p[i]; 35 while(n%p[i]==0) { 36 n/=p[i]; 37 tmp*=p[i]; 38 q++; 39 } 40 prod2*=q+1; 41 prod1*=((oword)tmp*tmp-1)/(p[i]*p[i]-1); 42 } 43 if(n!=1) { 44 prod1*=(qword)n*n+1; 45 prod2*=2; 46 } 47 printf("%llu ",prod1-prod2); 48 } 49 return 0; 50 }