出题人题解 | #手办#

手办

https://ac.nowcoder.com/acm/problem/18946

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

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

f(x)f(x)为整除xx(ab)(a * b)的有序对数

g(n)g(n)i=1nf(i)\sum_{i=1}^{n} f(i)

有了这个求和就简单了

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

那么g(x)g(x)求的就是(abc)x(a* b*c)\leq x的对数

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

这样保证了abca \leq b \leq c最后乘上全排列就ok了

对于a×a×aa \times a \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; 
} 

全部评论

相关推荐

面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
点赞 评论 收藏
分享
05-29 20:34
门头沟学院 C++
KarlAllen:得做好直接春招的准备。学历差的话,一是面试要求会比学历好的严格不少,二是就算面试通过了也会被排序。总之暑期和秋招对于学历差的就是及其不友好
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务