526互联

[数论]GCD&LCM&欧拉函——推柿子+例题

发布时间 2023-06-12 19:54:15作者: nannan4128

GCD&LCM&欧拉函——推柿子

一、\(\sum_{i = 1}^{n}[\gcd(i,n)=d]\)

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

\(=\sum_{i = 1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\)

\(=\phi(\frac{n}{d})\)

二、\(\sum_{i = 1}^{n}\gcd(i,n)\)

\(\sum_{i = 1}^{n}\gcd(i,n)\)

\(=\sum_{d|n}d\sum_{i = 1}^{n}[\gcd(i,n)=d]\)

\(=\sum_{d|n}\sum_{i = 1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\)

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

三、\(\sum_{i = 1}^{n}\sum_{j = 1}^{n}\gcd(i,j)\)

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

\(=\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{d|\gcd(i,j)}\phi(d)\)

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

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

\(=\sum_{d = 1}^{n}\phi(d)\lfloor n|d \rfloor^{2}\)

四、\(\sum_{i = 1}^{n}lcm(m,n)\)

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

\(\sum_{i = 1}^{n} lcm(i,n)\)

$ = \sum_{i = 1}^{n} \dfrac{i \times n}{\gcd(i,n)} $

\(= n \times\sum_{i = 1}^{n} \dfrac{i}{\gcd(i,n)}\)

\(\sum_{i = 1}^{n} \dfrac{i}{\gcd(i,n)}\)

\(=\sum_{d|n} \sum_{i=1}^{n} \dfrac{i}{d} [\gcd(i,n)=d]\)

\(= \sum_{d|n}\sum_{i = 1}^{\frac{n}{d}}i[\gcd(i,\frac{n}{d})=1]\)

\(= \sum_{d|n}\sum_{i = 1}^{d}i[\gcd(i,d)=1]\)

\(\because\gcd(i,d)=gcd(d-i,d)\)对于这样一对\(i+(d-i) = d\)

\(\sum_{i = 1}^{d}i [gcd(i, d) = 1]=\dfrac{d\times\phi(d)+1}{2}\)这里\(+1\)是对\(d=1\)的情况做一个修正

\(∴\sum_{i = 1}^{n} lcm(i,n)=n\times\)\(\dfrac{d\times\phi(d)+1}{2}\)

五、\(\sum_{x=0}^{m-1} [\ \gcd(a, m) = \gcd(a + x, m)\ ]\)

\(\sum_{x=0}^{m-1} [\ \gcd(a, m) = \gcd(a + x, m)\ ]\)

设\(\gcd(a,m)=d\)则有\(\gcd(\frac{a}{d},\frac{m}{d})=1\)

\(\therefore\gcd(\frac{a+x}{d},\frac{m}{d})=1\)

\(\gcd(\frac{a+x}{d},\frac{m}{d})=1\rightarrow\gcd(\frac{a}{d}+k,\frac{m}{d})=1\)其中\(k \in [0,\frac{m-1}{d}]\)

\(\therefore\)原题转化为求\([\frac{a}{d},\frac{a}{d}+\frac{m}{d})\)与\(\frac{m}{d}\)互质的数的个数。

这里是求$ [l , l+r)$ 与$ r$ 互质的数的个数，欧拉函数求的是 小于 \(r\) 且与 \(r\) 互质的数。其实这两者是相等的。那么答案就为\(\phi(\frac{m}{d})\)。

例题：

1.Benefit

Problem Statement

题意：使得 \(\operatorname{lcm}(a,b)=c\) 成立最小的 \(b\)，若没有满足条件的$ b$，输出 NO SOLUTION。

\(1≤t≤10^5，1\le a,c\le 10^7\)

solution

题解：

法一：

\(\operatorname{lcm} = \dfrac{ab}{\gcd(a,b)} = c\)

\(\dfrac{b}{\gcd(a,b)} = \dfrac{c}{a}\)

\(\because \dfrac{b}{\gcd(a,b)}\)是整数,那\(\dfrac{c}{a}\)也要是整数,即若\(c\bmod a \neq 0\)则输出NO SOLUTION

否则的话我们去找合适的\(b\)

令\(d = \dfrac{c}{a}\)，设函数\(f(a,d)\)为使得\(\dfrac{x}{\gcd(a,x)}=d\)成立的最小的\(x\),再分类讨论:

  1. 当\(gcd(a,d)=1\)时，显然\(x = d\)

  2. 当\(\gcd(a,d)>1\)时，设\(k = \gcd(a,x)\)代入\(f(a,d)\)得\(x = kd\)

    则有\(k = \gcd(a,kd)\)

    设\(\gcd(a,d)=g\),则\(\frac{k}{g}=\gcd(\frac{a}{g},\frac{d}{g}k)\)

    \(\because \dfrac{a}{g}\)和\(\dfrac{d}{g}\)已经是互质的,则\(\frac{k}{g}=\gcd(\frac{a}{g},k)\)

    移项得:\(\frac{k}{gcd(\frac{a}{g},{k})} = g\)

    通过递归求解\(f(\frac{a}{g},g)\)求得\(k\)

    最后答案为\(x = kd\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
/*
		lcm(a,b) = c;
		a*b/gcd(a,b) = c;
		b/gcd(a,b) = c/a;
		d = c/a;
		f(a,d) = x ==> x/gcd(a,x) = d;
		if(gcd(a,d)==1) x = d;
		else(gcd(a,d)>1)
		{
			设gcd(a,x) = k;
			x = dk;
			gcd(a,dk) = k;
			设gcd(a,d)  = g;
			gcd(a/g,dk/g) = k/g;
			a/g和d/g互质
			所以gcd(a/g,k) = k/g
			k/gcd(a/g,k) = g;
			求f(a/g,g);
		}
*/
int f(int a,int d)
{
	int g = gcd(a,d);
	if(g==1)return 1;
	return f(a/g,g);
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int a,c;
		cin>>a>>c;
	
		if(c%a)cout<<"NO SOLUTION\n";
		else
		{
			int d = c/a;
			cout<<d*f(a,d)<<endl;
		}
	}	
	return 0;
}

法二:我们可以很容易知道答案一定是质数,因为如果是合数那我们一定可以消去一个约数找到更优的。

同样对于每个\(a,c\)若\(c\bmod a \neq 0\)则无解，否则

\(lcm(a,b) = \dfrac{ab}{\gcd(a,b)}=c\)

\(\dfrac{b}{\gcd(a,b)} = \dfrac{c}{a}\) ,设\(b = \dfrac{c}{a}\),若\(\gcd(a,b)\neq 1\)就不断调整

理由如下:

令\(b = \dfrac{c}{a}\)，\(d = \gcd(a,b)\),若\(\gcd(a,b)\neq 1\),则就证明此时的\(a\)和\(b的最小公倍数\)肯定不是\(c\),

而是\(\dfrac{ab}{d}\),那么我们通过\(a = \dfrac{a}{d}和b = b\times d\)进行调整，保证了\(\dfrac{ab}{gcd(a,b)}=c\)仍成立的同时消去一个公因子

不断调整直到\(d=1\)，输出\(b\)就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
void solve(ll a,ll c)
{
	ll b,d;
	if(c%a)
	{
		cout<<"NO SOLUTION\n";
		return;
	}
	b=c/a;
	d=gcd(a,b);
	while(d!=1)
	{
		a/=d;
		b*=d;
		//保证a*b/gcd(a,b)==c的同时去掉了一个公因子
		d=gcd(a,b);
	}
	cout<<b<<endl;
	return;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll a,c;
		cin>>a>>c;
		// if(c%a)cout<<"NO SOLUTION\n";
		// else
		// {
		// 	ll t = c/a;
		// 	cout<<"t = "<<t<<endl;
		// 	ll g = gcd(t,a);
		// 	cout<<"g = "<<g<<endl;
		// 	cout<<t*g<<endl;
		// }
		solve(a,c);
	}
	return 0;
}

法三:

根据之前 b 为 \(\dfrac{c}{a}\) 的倍数就可以循环枚举 \(b\) 判断是否满足$ b = \dfrac{c}{a} \times \gcd(a,b)$。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b % a) {printf("NO SOLUTION\n");continue;}
        int x = b / a;
        for(int i = x;i <= b;i += x)
        {
            int gcd = __gcd(a,i);
            if(gcd * x == i) {printf("%d\n",i);break;}
        }
    }   
    return 0;
}

2.P1891 疯狂 LCM

Problem Statement

题意:

给定 \(n\)，求

\[\sum_{i = 1}^n \operatorname{lcm}(i, n) \]

其中 \(\operatorname{lcm}(i, j)\) 表示 \(i\) 和 \(j\) 的最小公倍数。

  • 对于 \(30\%\) 的数据，保证 \(T \leq 5\)，\(n \leq 10^5\)。
  • 对于 \(100\%\) 的数据，\(1 \leq T \leq 3 \times 10^5\)，\(1 \leq n \leq 10^6\)。

solution

$\sum_{i = 1}^{n} lcm(i,n) = \sum_{i = 1}^{n} \dfrac{i \times n}{\gcd(i,n)} $$= n \times\sum_{i = 1}^{n} \dfrac{i}{\gcd(i,n)}$

\(\sum_{i = 1}^{n} \dfrac{i}{\gcd(i,n)}\)

\(=\sum_{d|n} \sum_{i=1}^{n} \dfrac{i}{d} [\gcd(i,n)=d]\)
\(= \sum_{d|n}\sum_{i = 1}^{\frac{n}{d}}i[\gcd(i,\frac{n}{d})=1]\)这样让分母变为1,使得计算简化
\(= \sum_{d|n}\sum_{i = 1}^{d}i[\gcd(i,d)=1]\) 这里d倒着枚举

其中\(sum_{i = 1}^{d}i[gcd(i,d)==1]\) 表示与d互质的所有数之和
∵ \(\gcd(i,d)=gcd(d-i,d)\) 对于这样一对\(i+(d-i) = d\)
我们发现除了1之外都能找到这样一对，那么\(\sum_{i = 1}^{d}i [gcd(i, d) = 1]=\dfrac{d\times\phi(d)+1}{2}\)这里\(+1\)是因为如果d=1时,\(\dfrac{d\times\phi(d)}{2}=0\)是不对的，那\(+1\)之后呢,对于其他的没有影响对与d=1的情况有了一个修正，或者对d=1做一个特判也是可以的。

综上所述，最后答案为\(n\times\sum_{d|n}\dfrac{d\times\phi(d)+1}{2}\)，记得对\(\sum_{d|n}\dfrac{d\times\phi(d)+1}{2}\)做一个预处理，不然会T。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
const int MAXN=1e6;
bool check[MAXN+10];
ll phi[MAXN+10];
ll prime[MAXN+10],f[MAXN+10];
ll tot;
void phi_and_prime_table(int N){
    memset(check,0,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>N)
                break;
            check[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	phi_and_prime_table(MAXN);
	for(int i = 1;i<=MAXN;i++)
	{
		for(int j = i;j<=MAXN;j+=i)
		{
			f[j] += (i*phi[i]+1)/2;
		}
	}
	int t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		cout<<f[n]*n<<'\n';
	}
	return 0;
}

总结：通常\(\gcd\)和\(lcm\)的题目通常通过推柿子的方式与\(\phi\)练习起来运算。

3.P2303 [SDOI2012] Longge 的问题

Problem Statement

题意：给定一个整数 \(n\)，你需要求出 $\sum\limits_{i=1}^n \gcd(i, n)，其中 $$\gcd(i, n)$ 表示\(i\) 和 \(n\) 的最大公因数。

solution

\(\sum\limits_{i=1}^n \gcd(i, n)\)

我们令\(t(x)\)为\(gcd=x\)的数的个数

\(t(d) = \sum\limits_{i=1}^n [\gcd(i, n)=d]\) = \(\sum_{i = 1}^{n/d}[\gcd(i,\dfrac{n}{d})=1]=\sum_{d|n}d\times\phi(\frac{n}{d})\)

那么接下来我们只需要对\(n\)进行质因数分解即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<16)+10;
int n,tot,p[N];
bool flg[N];

void sieve(int n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
long long phi(long long x) {
    long long ans=x;
    for(int i=1;i<=tot&&1LL*p[i]*p[i]<=x;++i) {
        if(x%p[i]) continue;
        ans=ans/p[i]*(p[i]-1);
        while(x%p[i]==0) x/=p[i];
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	ll n;
	cin>>n;
	ll ans = 0;
	sieve(sqrt(n));
	for(ll i = 1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			ans += i*phi(n/i);
			if(i*i!=n)
				ans += n/i*phi(i);
		}
	}
	cout<<ans<<endl;
	return 0;
}

5.P2568 GCD

Problem Statement

题意:给定正整数\(n\)，求 \(1\le x,y\le n\) 且 \(\gcd(x,y)\) 为素数的数对 \((x,y)\) 有多少对。

solution

\(\gcd(ap,bp)=p\Rightarrow\gcd(a,b)=1\)

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

\(=\sum_{p\in prime}\sum_{i = 1}^{\frac{n}{p}}\sum_{j = 1}^{\frac{n}{p}}[\gcd(i,j)==1]\)

\(=\sum_{p\in prime}\sum_{i = 1}^{\frac{n}{p}}(2\times\sum_{j = 1}^{i}[\gcd(i,j)=1]-1)\)因为\(\gcd(i,j)=\gcd(j,i)\)所以我们枚举\(j\)的上界\(i\)，注意\(-1\)因为\(i=j\)时候有重复

\(=\sum_{p\in prime}(\sum_{i = 1}^{\frac{n}{p}}(2\times\phi(i))-1)\)

\(=\sum_{p\in prime}(2\times\sum_{i = 1}^{\frac{n}{p}}(\phi(i))-1)\)

我们可以用线性筛求出\(\phi(i)\)的值并预处理出其前缀和,最后枚举\(p\in\text{prime}\ \text{and}\ p\le n\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=10000000;
bool check[MAXN+10];
ll phi[MAXN+10];
ll prime[MAXN+10],sum[MAXN];
int tot;
void phi_and_prime_table(int N){
    memset(check,0,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>N)
                break;
            check[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
    for(int i=1;i<=N;++i) sum[i]=sum[i-1]+phi[i];
}


int main()
{
	int n;
	cin>>n;
	phi_and_prime_table(n);
	ll ans = 0;
	//gcd(a*p,b*p)=p <==> gcd(a,b) = 1
	for(int i = 0;i<tot;i++)
		ans += (2*sum[n/prime[i]]-1);
	cout<<ans<<endl;
	return 0;
}

6.Same GCDs

Problem Statement

题意：

求

​ \(\sum_{x=0}^{m-1} [\ \gcd(a, m) = \gcd(a + x, m)\ ]\)

多组测试数据, \(T \leq 50,\ 1 \leq a < m \leq 10^{10}\)

solution

解法：

设\(\gcd(a,m)=d\)则有\(\gcd(\frac{a}{d},\frac{m}{d})=1\)

又\(\because \gcd(a,m)=\gcd(a+x,m)\),\(\therefore\gcd(\frac{a+x}{d},\frac{m}{d})=1\)

\(\gcd(\frac{a+x}{d},\frac{m}{d})=1\rightarrow\gcd(\frac{a}{d}+k,\frac{m}{d})=1\)其中\(k \in [0,\frac{m-1}{d}]\)

\(\therefore\)原题转化为求\([\frac{a}{d},\frac{a}{d}+\frac{m}{d})\)与\(\frac{m}{d}\)互质的数的个数。

这里是求$ [l , l+r)$ 与$ r$ 互质的数的个数，欧拉函数求的是 小于 \(r\) 且与 \(r\) 互质的数。其实这两者是相等的。那么答案就为\(\phi(\frac{m}{d})\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
const int N=1e5;
ll n,tot,p[N];
bool flg[N];

void sieve(ll n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
long long phi(long long x) {
    long long ans=x;
    for(int i=1;i<=tot&&1LL*p[i]*p[i]<=x;++i) {
        if(x%p[i]) continue;
        ans=ans/p[i]*(p[i]-1);
        while(x%p[i]==0) x/=p[i];
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}

int main()
{
	int t;
	cin>>t;
	sieve(N);
	while(t--)
	{
		ll a,m;
		cin>>a>>m;
		ll g = gcd(a,m);
		/*
			gcd(a/g,m/g)==1
			gcd((a+x)/g,m/g)==1
			gcd(a/g+k,m/g)==1
			k = 0~(m-1)/g
			[a/g,(a+m)/g)与m/g互质
		*/
		a/=g,m/=g;
		cout<<phi(m)<<endl;
	}
	return 0;
}