首页 > 代码库 > 51nod 1244 莫比乌斯函数之和
51nod 1244 莫比乌斯函数之和
题目链接:51nod 1244 莫比乌斯函数之和
推荐学习博客:http://blog.csdn.net/skywalkert/article/details/50500009 然后,这题解法里面提到了,我就不打公式了,,,好好看大神的博客唉orz
用筛法预处理前N^(2/3)项,后面的记忆化搜索解决。还不会哈希唉,先用map了。
今晚自学感觉晕晕的,有空我还是要去练练其他题orz
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 using namespace std; 7 #define CLR(a,b) memset((a),(b),sizeof((a))) 8 typedef long long ll; 9 const int N = 6000000; 10 bool check[N+10]; 11 int prime[N+10]; 12 int mu[N+10]; 13 ll mu_sum[N+10]; 14 void Moblus(){ 15 CLR(check, false); 16 mu[1] = 1; 17 int tot = 0; 18 for(int i = 2; i <= N; i++){ 19 if( !check[i] ){ 20 prime[tot++] = i; 21 mu[i] = -1; 22 } 23 for(int j = 0; j < tot && i*prime[j] <= N; j++){ 24 check[i * prime[j]] = true; 25 if( i % prime[j] == 0){ 26 mu[i * prime[j]] = 0; 27 break; 28 } 29 else 30 mu[i * prime[j]] = -mu[i]; 31 } 32 } 33 for(int i = 1; i <= N; ++i) 34 mu_sum[i] = mu_sum[i-1] + mu[i]; 35 } 36 map<ll,ll> mp; 37 ll Mertens(ll n){ 38 if(n <= N) return mu_sum[n]; 39 if(mp.count(n)) return mp[n]; 40 ll ans = 1, ed; 41 for(ll i = 2; i <= n; i = ed+1){ 42 ed = n/(n/i); 43 ans -= (ed - i + 1)*Mertens(n/i); 44 } 45 return mp[n] = ans; 46 } 47 int main(){ 48 Moblus(); 49 ll a, b; 50 scanf("%lld%lld", &a, &b); 51 printf("%lld\n", Mertens(b) - Mertens(a-1)); 52 return 0; 53 }
51nod 1244 莫比乌斯函数之和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。