莫比乌斯反演 两种形式

2024-08-26 13:58

本文主要是介绍莫比乌斯反演 两种形式,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

莫比乌斯反演在数论中占有重要的地位,许多情况下能大大简化运算。那么我们先来认识莫比乌斯反演公式。

 

定理:是定义在非负整数集合上的两个函数,并且满足条件,那么我们得到结论

 

     

 

在上面的公式中有一个函数,它的定义如下:

 

    (1)若,那么

    (2)若均为互异素数,那么

    (3)其它情况下

 

 

对于函数,它有如下的常见性质:

 

    (1)对任意正整数

  

                            

 

        (2)对任意正整数

 

         

 

线性筛选求莫比乌斯反演函数代码。

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void Init()  
  2. {  
  3.     memset(vis,0,sizeof(vis));  
  4.     mu[1] = 1;  
  5.     cnt = 0;  
  6.     for(int i=2; i<N; i++)  
  7.     {  
  8.         if(!vis[i])  
  9.         {  
  10.             prime[cnt++] = i;  
  11.             mu[i] = -1;  
  12.         }  
  13.         for(int j=0; j<cnt&&i*prime[j]<N; j++)  
  14.         {  
  15.             vis[i*prime[j]] = 1;  
  16.             if(i%prime[j]) mu[i*prime[j]] = -mu[i];  
  17.             else  
  18.             {  
  19.                 mu[i*prime[j]] = 0;  
  20.                 break;  
  21.             }  
  22.         }  
  23.     }  
  24. }  


 

有了上面的知识,现在我们来证明莫比乌斯反演定理。

 

证明

 

 

证明完毕!

 

嗯,有了莫比乌斯反演,很多问题都可以简化了,接下来我们来看看莫比乌斯反演在数论中如何简化运算的。

 

 

题目:http://bz.cdqzoi.com/JudgeOnline/problem.php?id=2818

 

题意:给一个正整数,其中,求使得为质数的的个数,

 

分析:对于本题,因为是使得为质数,所以必然要枚举小于等于的质数,那么对于每一个质数,只

     需要求在区间中,满足有序对互质的对数。

 

     也就是说,现在问题转化为:在区间中,存在多少个有序对使得互质,这个问题就简单啦,因为

     是有序对,不妨设,那么我们如果枚举每一个,小于有多少个互素,这正是欧拉函数。所以

     我们可以递推法求欧拉函数,将得到的答案乘以2即可,但是这里乘以2后还有漏计算了的,那么有哪些呢?

     是且为素数的情况,再加上就行了。

 

代码:

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. #include <iostream>  
  2. #include <string.h>  
  3. #include <stdio.h>  
  4. #include <bitset>  
  5.   
  6. using namespace std;  
  7. typedef long long LL;  
  8. const int N = 10000010;  
  9.   
  10. bitset<N> prime;  
  11. LL phi[N];  
  12. LL f[N];  
  13. int p[N];  
  14. int k;  
  15.   
  16. void isprime()  
  17. {  
  18.     k = 0;  
  19.     prime.set();  
  20.     for(int i=2; i<N; i++)  
  21.     {  
  22.         if(prime[i])  
  23.         {  
  24.             p[k++] = i;  
  25.             for(int j=i+i; j<N; j+=i)  
  26.                 prime[j] = false;  
  27.         }  
  28.     }  
  29. }  
  30.   
  31. void Init()  
  32. {  
  33.     for(int i=1; i<N; i++)  phi[i] = i;  
  34.     for(int i=2; i<N; i+=2) phi[i] >>= 1;  
  35.     for(int i=3; i<N; i+=2)  
  36.     {  
  37.         if(phi[i] == i)  
  38.         {  
  39.             for(int j=i; j<N; j+=i)  
  40.                 phi[j] = phi[j] - phi[j] / i;  
  41.         }  
  42.     }  
  43.     f[1] = 0;  
  44.     for(int i=2;i<N;i++)  
  45.         f[i] = f[i-1] + (phi[i]<<1);  
  46. }  
  47.   
  48. LL Solve(int n)  
  49. {  
  50.     LL ans = 0;  
  51.     for(int i=0; i<k&&p[i]<=n; i++)  
  52.         ans += 1 + f[n/p[i]];  
  53.     return ans;  
  54. }  
  55.   
  56. int main()  
  57. {  
  58.     Init();  
  59.     isprime();  
  60.     int n;  
  61.     scanf("%d",&n);  
  62.     printf("%I64d\n",Solve(n));  
  63.     return 0;  
  64. }  


 

嗯,上题不算太难,普通的欧拉函数就可以搞定,接下来我们来看看它的升级版。

 

题意:给定两个数,其中,求为质数的有多少对?其中的范

     围是

 

分析:本题与上题不同的是不一定相同。在这里我们用莫比乌斯反演来解决,文章开头也说了它能大大简化

     运算。我们知道莫比乌斯反演的一般描述为:

 

     

 

     其实它还有另一种描述,本题也是用到这种。那就是:

 

     

 

     好了,到了这里,我们开始进入正题。。。

 

     对于本题,我们设

 

     为满足的对数

     为满足的对数

 

     那么,很显然,反演后得到

 

     因为题目要求是为质数,那么我们枚举每一个质数,然后得到

 

     

 

     如果直接这样做肯定TLE,那么我们必须优化。

 

     我们设,那么继续得到

 

     到了这里,可以看出如果我们可以先预处理出所有的对应的的值,那么本题就解决了。

 

     我们设,注意这里为素数,

 

     那么,我们枚举每一个,得到,现在分情况讨论:

 

     (1)如果整除,那么得到

 

       

 

     (2)如果不整除,那么得到

 

       

 

[cpp]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. #include <iostream>  
  2. #include <string.h>  
  3. #include <stdio.h>  
  4.   
  5. using namespace std;  
  6. typedef long long LL;  
  7. const int N = 10000005;  
  8.   
  9. bool vis[N];  
  10. int p[N];  
  11. int cnt;  
  12. int g[N],u[N],sum[N];  
  13.   
  14. void Init()  
  15. {  
  16.     memset(vis,0,sizeof(vis));  
  17.     u[1] = 1;  
  18.     cnt = 0;  
  19.     for(int i=2;i<N;i++)  
  20.     {  
  21.         if(!vis[i])  
  22.         {  
  23.             p[cnt++] = i;  
  24.             u[i] = -1;  
  25.             g[i] = 1;  
  26.         }  
  27.         for(int j=0;j<cnt&&i*p[j]<N;j++)  
  28.         {  
  29.             vis[i*p[j]] = 1;  
  30.             if(i%p[j])  
  31.             {  
  32.                 u[i*p[j]] = -u[i];  
  33.                 g[i*p[j]] = u[i] - g[i];  
  34.             }  
  35.             else  
  36.             {  
  37.                 u[i*p[j]] = 0;  
  38.                 g[i*p[j]] = u[i];  
  39.                 break;  
  40.             }  
  41.         }  
  42.     }  
  43.     sum[0] = 0;  
  44.     for(int i=1;i<N;i++)  
  45.         sum[i] = sum[i-1] + g[i];  
  46. }  
  47.   
  48. int main()  
  49. {  
  50.     Init();  
  51.     int T;  
  52.     scanf("%d",&T);  
  53.     while(T--)  
  54.     {  
  55.         LL n,m;  
  56.         cin>>n>>m;  
  57.         if(n > m) swap(n,m);  
  58.         LL ans = 0;  
  59.         for(int i=1,last;i<=n;i=last+1)  
  60.         {  
  61.             last = min(n/(n/i),m/(m/i));  
  62.             ans += (n/i)*(m/i)*(sum[last]-sum[i-1]);  
  63.         }  
  64.         cout<<ans<<endl;  
  65.     }  
  66.     return 0;  
  67. }  

这篇关于莫比乌斯反演 两种形式的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1108763

相关文章

hdu6053 TrickGCD 莫比乌斯反演

TrickGCD Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Problem Description You are given an array  A  , and Zhu wants to know there are how many d

android两种日志获取log4j

android   log4j 加载日志使用方法; 先上图: 有两种方式: 1:直接使用架包 加载(两个都要使用); 架包:android-logging-log4j-1.0.3.jar 、log4j-1.2.15.jar  (说明:也可以使用架包:log4j-1.2.17.jar)  2:对架包输入日志的二次封装使用; 1:直接使用 log4j 日志框架获取日志信息: A:配置 日志 文

c++11工厂子类实现自注册的两种方法

文章目录 一、产品类构建1. 猫基类与各品种猫子类2.狗基类与各品种狗子类 二、工厂类构建三、客户端使用switch-case实现调用不同工厂子类四、自注册方法一:公开注册函数显式注册五、自注册方法二:构造函数隐形注册总结 一、产品类构建 1. 猫基类与各品种猫子类 class Cat {public:virtual void Printer() = 0;};class

关于字符串转化为数字的深度优化两种算法

最近在做项目,在实际操作中发现自己在VC环境下写的字符串转化为整型的函数还是太过理想化了,或者说只能在window平台下软件环境中运行,重新给大家发两种函数方法: 第一个,就是理想化的函数,在VC环境下充分利用指针的优越性,对字符串转化为整型(同时也回答了某位网友的答案吖),实验检验通过: #include <stdio.h> #include <string.h> int rayatoi(c

Java构造和解析Json数据的两种方法(json-lib构造和解析Json数据, org.json构造和解析Json数据)

在www.json.org上公布了很多JAVA下的json构造和解析工具,其中org.json和json-lib比较简单,两者使用上差不多但还是有些区别。下面首先介绍用json-lib构造和解析Json数据的方法示例。 一、介绍       JSON-lib包是一个beans,collections,maps,java arrays 和XML和JSON互相转换的包,主要就是用来解析Json

通过Ajax请求后台数据,返回JSONArray(JsonObject),页面(Jquery)以table的形式展示

点击“会商人员情况表”,弹出层,显示一个表格,如下图: 利用Ajax和Jquery和JSONArray和JsonObject来实现: 代码如下: 在hspersons.html中: <!DOCTYPE html><html><head><meta charset="UTF-8"><title>会商人员情况表</title><script type="text/javasc

软文发稿相比其他广告形式有哪些持续性优势?

软文发稿在品牌宣发中具有显著的持续性优势,特别是在与其他广告形式的比较中更能体现这些特点。凭借其潜移默化的影响力、增强品牌权威性和公信力、持续性的曝光优势、精准触达目标受众的能力、强互动性与引导性,以及较高的性价比,已经成为品牌推广不可或缺的手段 一 长期存在与持续曝光 长时间的内容可见性     软文发表后,通常会长时间存在于各种平台上,无论是官网、博客、行业网站还是社交媒体帖子。读

苹果账号登录后端验证两种方式 python2

import jsonimport jwt import requests import json import base64def decode_jwt(jwt_token):try:header,payload,sign = jwt_token.split('.')except:return {},{},""header = json.loads(base64.urlsafe_b6

Python(TensorFlow和PyTorch)两种显微镜成像重建算法模型(显微镜学)

🎯要点 🎯受激发射损耗显微镜算法模型:🖊恢复嘈杂二维和三维图像 | 🖊模型架构:恢复上下文信息和超分辨率图像 | 🖊使用嘈杂和高信噪比的图像训练模型 | 🖊准备半合成训练集 | 🖊优化沙邦尼尔损失和边缘损失 | 🖊使用峰值信噪比、归一化均方误差和多尺度结构相似性指数量化结果 | 🎯训练荧光显微镜模型和对抗网络图形转换模型 🍪语言内容分比 🍇Python图像归一化

【python 爬虫】python如何以request payload形式发送post请求

普通的http的post请求的请求content-type类型是:Content-Type:application/x-www-form-urlencoded, 而另外一种形式request payload,其Content-Type为application/json import jsonurl = 'https://api.github.com/some/endpoint'payload