出题人题解 | #手办#

原题解链接：https://ac.nowcoder.com/discuss/149984

其实本来所有的手办是$WifeWife$的中文翻译的

设$f(x)f(x)$为整除$xx$的$(a\ast b)(a\; *\; b)$的有序对数

$g(n)g(n)$ 为 ${\sum }_{i=1}^{n}f(i)\backslash sum\_\{i=1\}^\{n\}\; f(i)$

有了这个求和就简单了

另$a\ast b\ast c=xa*b*c=\; x$对于$f(x)f(x)$我们需要求的就是三元组$(a,b,c)(a,\; b,\; c)$的个数

那么$g(x)g(x)$求的就是$(a\ast b\ast c)\le x(a*\; b*c)\backslash leq\; x$的对数

我们可以先求对$(a\le b\le c)(a\; \backslash leq\; b\; \backslash leq\; c)$的三元组计数,那么$aa$只要枚举到三次根下$nn$就好了,$bb$从剩下的$\sqrt{\frac{n}{a}}\backslash sqrt\{\backslash frac\{n\}\{a\}\}$中枚举得到

这样保证了$a\le b\le ca\; \backslash leq\; b\; \backslash leq\; c$最后乘上全排列就ok了

对于$a\times a\times aa\; \backslash times\; a\; \backslash times\; a$它的全排列只有$11$个

所以枚举的$a,b,ca,b,c$不能重复，对于有两个数相同的全排列只有$33$个，也要去重。

#include<bits/stdc++.h> 
using namespace std; 
#define LL long long 
using namespace std;
const int mod = 2333; 
LL n,ans,tmp;

int main() { 
        cin >> n; 
    	for(LL a = 1,v; a * a <= (v = n / a);++ a,++ ans)  
    	    for(LL b = a + 1;b * b <= v;++ b)  
    	        tmp += n / (a * b) - b; 
    	ans += tmp * 6;  
    	tmp = 0; 
    	for(LL a=1,v;(v = a * a) <= n;++ a) {  
    	    tmp += n / v;  
    	    if(a * a <= n / a) tmp --;   
    	}   
   	 	ans += tmp*3;  
   	 	cout << ans % mod; 
    return 0; 
}