首页 > 其他分享 >[数论]数论函数/莫比乌斯反演

[数论]数论函数/莫比乌斯反演

时间：2023-06-29 22:12:00浏览次数：42  
标签：函数 数论 sum mu 反演 int 莫比 quad cases

数论函数/莫比乌斯反演

1.1积性函数

数论函数：可以认为是定义在整数上的函数。

1)积性函数定义

(a,b) = 1,f(a,b) = f(a)f(b)

2)积性函数性质

  1. 对于积性函数\(f\)，是被所有\(p^e\)处的值决定的

    a = 1,f(b) = f(1)f(b)

​ \(f(60) = f(4)\times f(15) = f(4)\times f(3)\times f(5)\)

​ \(n = \prod p^{ei}\)

​ \(f(n) = \prod f(pi^{ei})\)

​ 对于\(f(4)\)的话就没有办法把它表示成更小的素数幂的形式了，因为\(4 = 2\times 2\)显然\(2\)和\(2\)不互质

  1. (重要！)积性函数\(\times\)积性函数还是积性函数

1.2 、完全积性函数

1)定义

f(a,b) = f(a)f(b) 不要求(a,b) = 1

\(n = \prod p^{ei}\)

\(f(n) = \prod f(pi)^{ei}\)

  1. \(f(x) = 1\)
  2. \(f(x) = x\) \(f(x) = \sqrt{x}\) \(f(x) = x^2\)
  3. $ y= \begin{cases} 1,\quad x= 1\\ 0, \quad x\neq 1 \end{cases} \tag{1} $

1.3常见积性函数

①\(id(x) = x\)

②常数函数\(I(x) = 1\)

③单位函数$$ e(x)= \begin{cases} 1, \quad x= 1\\ 0, \quad x\neq 1 \end{cases} $$
\(=[x = 1](bool)\)

④欧拉函数\(\phi(n) = n\prod_{p|n}(1-\dfrac{1}{p})\)

\(\phi(p^e) = (1-\dfrac{1}{p})*p^e = p^e-p^{e-1}\)

⑤因子函数\(d(n)\)因子个数

\(d(p^e) = e+1\) \((p^0p^1...p^e)\)

⑥\(\sigma(n)\)因子和

\(\sigma(p^e) = p^0+p^1+...+p^e = \dfrac{p^{e+1}-1}{p-1}\)

⑦\(\mu(n)\)莫比乌斯函数

1.4 莫比乌斯函数

\[\mu(p^e)= \begin{cases} 1,\quad e= 0\\ 0, \quad e= 1 \\ 0 ,e\geq2\end{cases} \tag{1} \]

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk \\ 0 ,n有平方因子\end{cases} \tag{1} \]

1 2 3 4 5 6 7 8 9 10
1 -1 -1 0 -1 1 -1 0 0 1

性质：

\(\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}\)

即 ：\(\sum_{d|n}\mu(d) = e(n),\mu*1 = e\)

1.5线性筛求积性函数

线性筛：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
bool is_pri[maxn];
int pri[maxn];
int cnt;

void init(int n)
{
	memset(is_pri, true, sizeof(is_pri));
	is_pri[1] = false;
	cnt = 0;
	for (int i = 2; i <= n; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

由于一个正整数(除\(1\)外)可以通过质因数分解得到，对于非\(1\)的正整数都有：

\(n = p_1^{e_1}*p_2^{e_2}*...*p_k^{e_k}\)

根据积性函数定义，对于一个积性函数\(f(n)\)有:

\(f(n) = f(p_1^{e1})\times f(p_2^{e2})\times ...\times f(p_k^{ek}) = \prod f(p_i^{ei})\)
也就是说我们可以根据质因子推导出由该因子组成的合数。

对于一个合数有:

\(f(n) = f(p_1^{e1})\times f(\dfrac{n}{p_1^{e1}})\)

我们可以用线性筛帮助我们在\(O(n)\)求出\(n\)以内的积性函数值

定义：\(p[i]为i\)的最小质因子，\(pr[cnt]\)记录当前筛出的\(cnt\)个质数,\(pe[i]\)是\(p_1^{e_1}\)的值(标准分解里面的第一项)

  1. 求出\(pe[i]\).

  2. 若\(i\neq pe[i]\)说明是合数，我们直接递推\(f(i) = f(pe[i])\times f(\dfrac{i}{pe[i]})\)

    若\(i = pe[i]\)刚好是素数幂次，一般能从\(p^{e-1}\)推出\(p^e\)

因子个数：\(d(p^e) = d(p^{e-1})+1\)

因子和：\(\sigma(p^e) = \sigma(p^e-1)+p^e\)

欧拉函数：\(\phi(p^e) = \dfrac{i}{p_i}*(p_{i}-1)\)

莫比乌斯函数：$ \mu(i)= \begin{cases} -1,\quad i= p[i]
\\ 0\end{cases} \tag{1} $

void init(int n)//求各个函数的最小素数因子和指数
{
   p[1] = 1;
   for(int i = 2;i<=n;i++)
   {
   	if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
   	for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
   	{
   		p[i*pr[j]] = pr[j];
   		if(p[i]==pr[j])//i和i*pr[j]的最小的素因子是一样的
            {
               //比如pe[5^3*7] = pr[5^2*7]*5
   			pe[i*pr[j]] = pe[i]*pr[j];
   			break;
   		}
   		else//说明被更小的质因子筛到了
   		{
   			pe[i*pr[j]] = pr[j];
   		}
		}
   } 
}


//写法1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn =1000010;
int p[maxn],pr[maxn/5],pe[maxn];
int cnt;

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

uint f[N],a,b,ans;


void compute(int n,function<void(int)>calcpe){
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pr[i])calcpe(i);
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;
}


int main()
{
	cin>>n>>a>>b;
	init(n);

	//因子个数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])
			f[i] = f[i/p[i]]+1;//i/p[i]==>p^{e-1}
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;

	//因子和
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])f[i] = f[i/p[i]]+i;
		else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;


	//欧拉函数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])f[i] = i/p[i]*(p[i]-1);
		else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;

	//莫比乌斯函数
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i]){
			if(i==p[i])f[i] = (uint)(-1);
			else f[i] = 0;
		}else f[i] = f[pe[i]]*f[i/pe[i]];
	}
	for(uint i = 1;i<=n;i++)
		ans ^= (a*i*f[i]+b);
	cout<<ans<<endl;
	return 0;
}


//写法2
#include<bits/stdc++.h>
using namespace std;
const int maxn =20010000;
int p[maxn],pr[maxn/5],pe[maxn];
int cnt;

void init(int n)//求各个函数的最小素数因子和指数
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,pe[i] = i,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])//i和i*pr[j]的素因子是一样的
			{
				pe[i*pr[j]] = pe[i]*pr[j];
				break;
			}
			else
			{
				pe[i*pr[j]] = pr[j];
			}
 		}
	}
}

//如果单求phi
int phi[maxn];
void phi(int n)
{
	p[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(!p[i])p[i] = i,phi[i] = i-1,pr[++cnt] = i;
		for(int j = 1;j<=cnt&&i*pr[j]<=n;j++)
		{
			p[i*pr[j]] = pr[j];
			if(p[i]==pr[j])
			{
				phi[i*pr[j]] = phi[i]*pr[j];
				break;
			}else{
				phi[i*pr[j]] = phi[i]*(pr[j]-1);
			}
		}
	}
}

unsigned int f[maxn],a,b,ans,n;


void compute(int n,function<void(int)>calcpe){
	ans = 0;
	f[1] = 1;
	for(int i = 2;i<=n;i++)
	{
		if(i==pe[i])calcpe(i);
		else f[i] = f[pe[i]]*f[i/pe[i]];//积性函数，把这两个乘起来
	}
	for(int i = 1;i<=n;i++)
		ans ^= (a*(unsigned int)i*f[i]+b);
	cout<<ans<<endl;
}


int main()
{
	cin>>n>>a>>b;
	init(n);
	//因子个数
	compute(n,[&](int x){
		f[x] = f[x/p[x]] + 1;
	});

	//因子和
	compute(n,[&](int x){
		f[x] = f[x/p[x]] + x;
	});


	//欧拉函数
	compute(n,[&](int x){
		f[x] = x/p[x]*(p[x]-1);
	});

	//莫比乌斯函数
	compute(n,[&](int x){
		f[x] = x==p[x]?-1:0;
	});
	return 0;
}

2.1迪利克雷卷积

2.1.1定义

image

\(h(n) = \sum_{d|n}f(d)g(\dfrac{n}{d}) = \sum_{d_1d_2 = n}f(d_1)g(d_2)\)

✳常见函数

\(e\)是单位函数，\(e(n)=[n=1]\) ， \(e\) 满足 \(f = f ∗ e\),即任何一个函数卷上\(e\) 都等于原函数。

\(I\)是常数函数， \(I ( n ) = 1\)。
\(Id\) 是恒等函数，\(Id(n)=n\)
\(\mu\) 是莫比乌斯函数$$ \mu(n)= \begin{cases} 1,\quad n= 1\ (-1)^k, \quad n = p1p2...pk \ 0 ,n有平方因子\end{cases} \tag{1} $$

$ \phi$ 是欧拉函数，$ \phi(n)=\sum_{d\leq n}[gcd(d,n)=1]$欧拉函数就是小于 \(n\) 的与它互质的数的个数。
\(\sigma\)是约数函数，\(\sigma(n)=\sum_{d|n}d\)
$ d$ ，约数函数就是$ n$ 的约数和。

✳迪利克雷卷积函数

将上述数论函数两两做卷积，可以得到一些新的数论函数：

除数函数与幂函数

image

欧拉函数与恒等函数

image

2.1.2性质

  1. 符合交换律和结合律
  2. (重要)\(f\)和\(g\)是积性函数=>\(f*g\)是积性函数

image

3.1莫比乌斯反演

莫比乌斯函数：

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk(奇数个质因子-1，偶数个就是1) \\ 0 ,n有平方因子\end{cases} \tag{1} \]

性质：

\(\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}\)

即 ：\(\sum_{d|n}\mu(d) = e(n),\mu*1 = e\)

3.1.1形式

\(f(n) = \sum_{n|d}g(d)=>g(n)= \sum \mu(\dfrac{n}{d})f(d)\)

\(g = f*\mu\)

\(1*\mu = e\)即：\(\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}\)

证明：

\(f(p^e) = \sum_{d|p^e} = \sum_{d|p^e}\mu(d)\)

\(e>=1\)，\(f(p^e) = \mu(1)+\mu(p)+\mu(p^2)+...+\mu(p^e)\)

\(\mu(1) = 1,\mu(p) = -1\)，后面都等于\(0\)

所以对于任何\(e\)不等于1的值都是0

\(\because f = f*e,f = g*1\)

在两边同乘一个\(\mu\)得：\(f*\mu = (g*1)*\mu =>f*\mu = g*(1*\mu)\)

又因为\(1*\mu = e，g*e = g\)，所以\(f*\mu = g\)

\(g(n) = \sum_{d|n}f(d)*\mu(\frac{n}{d})\)

\(f*(\mu*1) = g*1=>f*e = g=>f =g\)

即可以推出：\(f(n) = \sum_{d|n}g(d)\)

3.1.2莫比乌斯反演公式

约数的莫比乌斯反演：
若：\(f(n) = \sum_{d|n}g(d)\)

则：\(g(n) = \sum_{d|n}\mu(d)f(\dfrac{n}{d})\)

倍数的莫比乌斯反演：
若：\(f(n) = \sum_{d|n}g(d)\)
则：\(g(n) = \sum_{d|n}\mu(\dfrac{n}{d})f(d)\)

3.1.3构造

典例：求\(\sum_{i = 1}^{n}\sum_{j = 1}^{m}[gcd(i,j)==d]\)

不妨记\(g(x) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j)==d]\)

任何让我们构造一个\(f(x)\)，这里我们需要用到第二组莫比乌斯反演公式。

那么\(f(x)\)是什么嘞？根据公式可知是若干个\(g(x)\)的和。记\(N = min(n,m)\)，即\(\gcd\)的上限，我们可以得到\(f(d) = g(d)+d(2d)+g(3d)+...+g(\lfloor\dfrac{N}{d}\rfloor)\)

即:\(f(d) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j)\bmod d==0]\)

写成公式形式就是：\(g(d) = \sum_{d|p}\mu(\dfrac{p}{d})f(p)\)

接下来问题就是如何求\(f(x)\)。\(f(x)\)是满足\(\gcd(i,j)\)是\(d\)的倍数的数对，显然有\(f(x) = \lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{x}\rfloor\)

\(g(n) = \sum_{d = 1}^{n}\mu(\dfrac{n}{d})*f(d)\)

eg.莫比乌斯反演

题意：

给定一个函数\(f(1),f(2),…,f(n)，\)已知\(f(n)=\sum_{d|n}g(d)\)，求\(g(1),g(2),…,g(n)\)。

思路：

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk \\ 0 ,n有平方因子\end{cases} \tag{1} \]

\(f(n) = \sum_{n|d}g(d)=>g(n)= \sum \mu(\dfrac{n}{d})f(d)\)

\(f = g*\mu\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1E6+10;
unsigned int A,B,C;
int n,cnt,f[N],p[N],mu[N],pr[N],g[N];
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%u%u%u", &n, &A, &B, &C);
    for (int i = 1; i <= n; i++)
        f[i] = rng61();
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=n;i++)
    {
        if(!p[i])p[i] = i,mu[i] = (unsigned int)-1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&pr[j]*i<=n;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }
            else
                mu[i*pr[j]] = (unsigned int)-mu[i];
        }
    }
    //g = f*mu
    //g[n] = sum_{d|n} f[d]*mu[n/d]
    //g[n] = sum_{n = d1*d2} f[d1]*mu[d2]
    for(int d1 = 1;d1<=n;d1++)
        for(int d2 = 1;d1*d2<=n;d2++)
            g[d1*d2] += f[d1]*mu[d2];
    unsigned int ans = 0;
    for(int i = 1;i<=n;i++)ans^=g[i];
    cout<<ans<<endl;
}

法二：

\(f(n) = \sum_{d|n}g(d)\)

\(g(i) = f(i)-\sum_{d|i,d\neq i}g(d)\)

eg2互质数对

题意：

\(T\)组询问，每次给两个数\(n,m\)，求有多少对\((i,j)\)满足1\(≤i≤n,1≤j≤m\)并且\(i,j\)互质。

思路：

\(\sum_{i<=i<=n,1<=j<=m}[(i,j)==1]=\sum e((i,j))\)

\(e(n) = [n==1]\)

\(e = 1*\mu\)

\(e(n) = \sum_{d|n}\mu(d)\)

\(1*\mu = e\)即：\(\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}\)

\(\sum_{i=1}^{n}\sum_{j = 1}^{m}[\gcd(i,j)==1]\)

\(=\sum e((i,j)) = \sum_{i,j}\sum_{d|(i,j)}\mu(d)\)

我们把\(\gcd(i,j)\)转化为\(d|i\)且\(d|j\)

$ = \sum_{i=1}^{n}\sum_{j = 1}^{m}\mu(d)[d|i][d|j]$

$ = \sum_{d = 1}^{n}\mu(d)\sum_{j = 1}^{m}[d|i][d|j]$

\(=\sum_{d = 1}^{n}\mu(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d} \rfloor\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10100000, M = 10000000;
int p[N],pr[N/5],n,cnt;
int mu[N],smu[N];
int main()
{
    p[1] = 1,mu[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,mu[i] = -1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                mu[i*pr[j]] = 0;
                break;
            }else{
                mu[i*pr[j]] = -mu[i];
            }
        }
    }
    for(int i = 1;i<=M;i++)
        smu[i] = smu[i-1]+mu[i];
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        ll ans = 0;
        //for(i~n)因为如果for(1~m)的话,n/l就已经是0了
        for(int l = 1;l<=n;l++)
        {
            int r = min(n/(n/l),m/(m/l));//在[l,r]里面n/l和m/l都是不变的
            ans += 1ll*(smu[r]-smu[l-1])*(n/l)*(m/l);
            l = r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

eg3.gcd之和

题意：

T组询问，每次给两个数\(n,m\)，求\(\sum_{i = 1}^{n}\sum_{j = 1}^{m}(i,j)\)

思路：

\[\mu(n)= \begin{cases} 1,\quad n= 1\\ (-1)^k, \quad n = p1p2...pk \\ 0 ,n有平方因子\end{cases} \tag{1} \]

性质：\(\sum_{d|n}\mu(d) = \begin{cases} 1,\quad n=1\\\ 0, \quad n\neq 1\end{cases} \tag{1}\)

\(id*\mu = \phi\)

\(\sum_{d|n}\phi(d) = n\)

\(\sum_{d|p^e}\mu(d)(\dfrac{p^e}{d})\)

只有当\(d = 1和d = p\)的时候有值，其他都是0

\(d = 1时，\mu(d) = 1,d = p时，\mu(d) = -1\)

\(p^e-p^{e-1} = \phi(p^e)\)

所以：\(\sum_{i = 1}^{n}\sum_{j = 1}^{m}(i,j) = \sum_{d = 1}^{n}\phi(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10100000, M = 10000000;
ll p[N],pr[N/5],n,cnt;
ll phi[N],sphi[N];
int main()
{
    p[1] = 1,phi[1] = 1;
    for(int i = 2;i<=M;i++)
    {
        if(!p[i])p[i] = i,phi[i] = i-1,pr[++cnt] = i;
        for(int j = 1;j<=cnt&&i*pr[j]<=M;j++)
        {
            p[i*pr[j]] = pr[j];
            if(p[i]==pr[j])
            {
                phi[i*pr[j]] = phi[i]*pr[j];
                break;
            }else{
                phi[i*pr[j]] = phi[i]*(pr[j]-1);
            }
        }
    }
    for(int i = 1;i<=M;i++)
        sphi[i] = sphi[i-1]+phi[i];
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        if(n>m)swap(n,m);
        ll ans = 0;
        //for(i~n)因为如果for(1~m)的话,n/l就已经是0了不用算了
        for(int l = 1;l<=n;l++)
        {
            int r = min(n/(n/l),m/(m/l));//在[l,r]里面n/l和m/l都是不变的
            ans += 1ll*(sphi[r]-sphi[l-1])*(n/l)*(m/l);
            l = r;
        }
        cout<<ans<<endl;
    }
    return 0;
}

✳总结做题技巧

对于所有带\(\gcd\)的

\(\sum_{i = 1}^{n}\sum_{j = 1}^{m}f((i,j))\)

对于以上我们都能找到数论函数\(g\)满足\(f(n) = \sum_{d|n}g(d)\),即\(g = f*\mu\)

\(f((i,j)) = \sum_{d|(i,j)}g(d)\)

我们把\(d\)提出来

$\sum_dg(d)\sum_{1<=i<=n,1<=j<=m,d|i,d|j}1 $

\(= \sum_{d}g(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor\)

以上方法对所有带\(\gcd\)的均适用

标签：函数,数论,sum,mu,反演,int,莫比,quad,cases
From： https://www.cnblogs.com/nannandbk/p/17515322.html

相关文章

  • 初等数论
    初等数论\(\mathcal{P}art\)1.基础概念整除对两个正整数\(a\)，\(b\)（\(b\lea\)），如果存在一个整数\(k\)使得\(a=kb\)，则称\(b\)整除\(a\)，记作\(b|a\)带余除法对任何整数\(a\)和正整数\(b\)，一定存在一个整数\(r\in[0,b)\)和一个整数\(k\)，使得\(a=kb+r\)，称上式......
  • 莫比乌斯反演 学习笔记
    炫酷反演魔术！莫反会用到的具体性质证明先不写，先写题。与其说是学习笔记，不如说是简要的题解集合。不太想贴太多代码啊，翻起来很烦。P3455[POI2007]ZAP-Queries很基础的一道题。令\(a\leb\)，考虑\(k=1\)的情况。\[\begin{aligned}ans&=\sum\limits_{i=1}^a\sum\limits_{j=......
  • Dreaming of Freedom(数论,贪心)
    用nsqrt(n)的时间复杂度就能过//DreamingofFreedom:https://codeforces.com/problemset/problem/1826/C#include<bits/stdc++.h>//#defineintlonglongusingnamespacestd;constintN=1e5+10,mod=1e9+7;strings;intn,t,a[N],f[N],res,num,ans,m;boolvis[N];i......
  • 数论
    类欧几里德\(\text{令}\spacef(a,b,c,n)=\sum_{i=1}^n\lfloor\frac{ai+b}{c}\rfloor\)\(f(a,b,c,n)=\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor+f(a\%c,b\%c,c,n)\)第二类斯特林数求自然幂和$\sum_{i=1}^ni^k=\sum_{i=1}^n\sum_{......
  • bzoj 2839. 集合计数 二项式反演
    集合计数设fi表示恰好交集为k的方案数。设gi表示交集至少为k的方案数。\(g_i=\sum_{j=i}^{n}C(j,i)f_j\)由二项式反演得：\(f_k=\sum_{i=k}^{n}(-1)^{i-k}C(i,k)g_i\)考虑\(g_i\)的求出，钦定\(i\)个数必选那么剩下\(n-i\)个数每个数可选可不选\(2^{n-i}\)但这道题我们选出的......
  • Add Modulo 10(数论,思维,数学,规律)
    思路：找规律情况一:尾数为5或0为5时进行一次操作变成0的情况。而尾数是 0 时操作无意义，所有数必须相等。情况二：尾数为 1,3,7,9可进行一次操作变成情况三。情况三：尾数为 2,4,6,8我们通过找规律发现：2⇒4⇒8⇒16⇒224⇒8⇒16⇒22⇒246⇒12⇒14⇒18⇒268⇒16⇒22⇒24⇒28......
  • 【蓝桥杯_真题演练】第九届C/C++省赛B组_C-乘积尾零（C++_数论）
    Problem如下的10行数据，每行有10个整数，请你求出它们的乘积的末尾有多少个零？56504542355447394641143871907390432927587949611356595245743230514434670435949937117368663397475975573070228714539899148657223135117040145510512072928809......
  • 【蓝桥杯_真题演练】第十届C/C++省赛B组_H-等差数列（C++_gcd_数论）
    ProblemProcess在输入的时候先去重，然后进行排序，至于他们的公差p则需要计算每两个相邻数值之间差值的最大公因数，最终的结果应该是Code#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintn,a[100010],cnt;set<int>s;intgcd(inta,intb){ returnb==......
  • P1062 数列(C++_数论)
    题目描述给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：（该序列实际上就是：)请你求出这个序列的第N项的值（用10进制数表示）。例如，对于k=3，N=100，正确答案应该是981。输入格式2个正整数，用一个空格隔开：输出格式1个正整......
  • P1582 倒水（C++_数论_进制）
    题目描述一天，CC买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着~~CC发现瓶子实在太多了，于是他决定保留不超过K个瓶子。每次他选择两个当前含水量相同的瓶子，把一个瓶子的水全部倒进另一个里，然后把空瓶丢弃。(不能丢弃有水的瓶子)显然在某些情况下CC无法达到目标，比......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99