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

Nannan Lv5
  2023-09-08 11:10 2023-09-08 11:10 Created   2024-09-30 19:31:28 2024-09-30 19:31:28 Updated      

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

一、

二、

三、

四、

LCMSUM

对于这样一对

这里是对的情况做一个修正

后面可以预处理出来，枚举d的倍数。

1
2
3
4
5
6
7
for(int i = 1;i<=n;i++)
  {
      for(int j = 1;i*j<=n;j++)
      {
          ans[i*j] += (i==1?1:1ll*phi[i]*i/2);
      }
  }

五、

设则有

其中

原题转化为求与互质的数的个数。

这里是求 与 互质的数的个数，欧拉函数求的是 小于 且与 互质的数。其实这两者是相等的。那么答案就为。

例题：

1.Benefit

Problem Statement

题意：使得 成立最小的 ，若没有满足条件的，输出 NO SOLUTION。

，

solution

题解：

法一：

是整数,那也要是整数,即若则输出NO SOLUTION

否则的话我们去找合适的

令，设函数为使得成立的最小的,再分类讨论:

  1. 当时，显然

  2. 当时，设代入得

    则有

    设,则

    和已经是互质的,则

    移项得:

    通过递归求解求得

    最后答案为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}

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

同样对于每个若则无解，否则

,设,若就不断调整

理由如下:

令，,若,则就证明此时的和的最小公倍数肯定不是,

而是,那么我们通过和进行调整，保证了仍成立的同时消去一个公因子

不断调整直到，输出就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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 为 的倍数就可以循环枚举 判断是否满足。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}

法四：唯一分解定理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int b[N],p[N],cnt;
ll qmi(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int a,c;
        cin>>a>>c;
        if(c%a){
            cout<<"NO SOLUTION\n";
            continue;
        }
        if(a==1){
            cout<<c<<"\n";
            continue;
        }
        cnt = 0;
        int ans = 1;
        for (int i = 2; i <= c / i; i++)
        {
            if (c % i == 0)
            {
                b[++cnt] = i;
                int s = 0;
                while (c % i == 0)
                {
                    c = c / i;
                    s++;
                }
                p[cnt] = s;
            }
        }
        if (c > 1)b[++cnt] = c,p[cnt] = 1;  

        for(int i = 1;i <= cnt; i++)
        {
            int s = 0;
            while(a % b[i]==0)
            {
                a/=b[i];
                s++;
            }
            if(s<p[i])ans *= qmi(b[i],p[i]);
        }
        cout<<ans<<"\n"; 
    }


    return 0;
}

2.P1891 疯狂 LCM

Problem Statement

题意:

给定 ，求

其中 表示 和 的最小公倍数。

  • 对于 的数据，保证 ，。
  • 对于 的数据，，。

solution


这样让分母变为1,使得计算简化
这里d倒着枚举

其中 表示与d互质的所有数之和
∵ 对于这样一对
我们发现除了1之外都能找到这样一对，那么这里是因为如果d=1时,是不对的，那之后呢,对于其他的没有影响对与d=1的情况有了一个修正，或者对d=1做一个特判也是可以的。

综上所述，最后答案为，记得对做一个预处理，不然会T。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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;
}

总结：通常和的题目通常通过推柿子的方式与联系起来运算。

3.P2303 [SDOI2012] Longge 的问题

Problem Statement

题意：给定一个整数 ，你需要求出 ，其中 表示 和 的最大公因数。

solution

我们令为的数的个数

=

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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

题意:给定正整数，求 且 为素数的数对 有多少对。

solution

因为所以我们枚举的上界，注意因为时候有重复

我们可以用线性筛求出的值并预处理出其前缀和,最后枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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

题意：

求

​

多组测试数据,

solution

解法：

设则有

又,

其中

原题转化为求与互质的数的个数。

这里是求 与 互质的数的个数，欧拉函数求的是 小于 且与 互质的数。其实这两者是相等的。那么答案就为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}
  • Title: GCD&LCM&欧拉函——推柿子
  • Author: Nannan
  • Created at : 2023-09-08 11:10:00
  • Updated at : 2024-09-30 19:31:28
  • Link: https://redefine.ohevan.com/2023/09/08/二(1)、GCD&LCM&Eluer推柿子/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
GCD&LCM&欧拉函——推柿子
  1. GCD&LCM&欧拉函——推柿子
    1. 一、
    2. 二、
    3. 三、
    4. 四、
    5. 五、
    6. 例题：
    7. 1.Benefit
      1. Problem Statement
      2. solution
    8. 2.P1891 疯狂 LCM
      1. Problem Statement
      2. solution
    9. 3.P2303 [SDOI2012] Longge 的问题
      1. Problem Statement
      2. solution
    10. 5.P2568 GCD
      1. Problem Statement
      2. solution
    11. 6.Same GCDs
      1. Problem Statement
      2. solution