GCD&LCM practice

Nannan Lv5
  2023-11-06 17:41 2023-11-06 17:41 Created   2024-09-30 19:22:52 2024-09-30 19:22:52 Updated      

GCD&LCM practice

1.GCD and LCM - HDU 4497 GCD和LCM性质

题意：给你两个正整数和,你可以说出有多少组解满足并且

注意和这样是两个不同的解。

思路:从的性质考虑：

  1. 若，则

显然，若是无解的，那下面我们来看有解的情况：

转化为

转化为

那么现在问题转化为：满足互质的，且他们的

因为要满足互质的的条件，那么以{}为例，至少有一个是。

合法的情况是：

1){} 排列方式3种

2){} 排列方式3种

3){～} 排列方式种

综上，对于每一位有$3+3+(e_1-1)6 = 6e_1$

那么接下来问题转化为对进行质因数分解，再求种类数即可。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll G,L;
		cin>>G>>L;
		if(L%G)
		{
			cout<<0<<endl;
			continue;
		}
		ll n = L/G;
		ll ans = 1;
		for(int i = 2;i<=n/i;i++)
		{
			if(n%i==0)
			{
				ll cnt = 0;
				while(n%i==0)
					n/=i,cnt++;
				ans*= 6ll*cnt;
			}
		}
		if(n>1)
			ans*=6ll;
		cout<<ans<<endl;
	}
	return 0;
}

2.hide handkerchief - HDU 2104 互素判定

题意：给你一个序列～，在给你一个数,从第一个开始，每次隔个进行访问，问这样能否把～都访问到？

思路：如果从一开始到现在一共走了步，那么现在位置就是,很显然，如果当前访问的这个节点之前被访问过，且当前还有节点未被访问，那之后也不会被访问到，那肯定是不能访问完的。

根据上述分析可知：如果且时的结果是。

我们化简一下$KM\bmod N = 0。有因为是最小的K满足这个柿子，那么NM是N的最小倍数是N那么他们的最大公约数自然是1。所以只要\gcd(N,M)=1$即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}


int main()
{
	while(1)
	{
		ll n,m;
		cin>>n>>m;
		if(n==-1&&m==-1)break;
		ll g = gcd(n,m);
		if(g!=1)cout<<"POOR Haha\n";
		else cout<<"YES\n";
	}
	return 0;
}

3.Least common multiple - HDU 3092 GCD+完全背包

题意：如果给你一个数，我们把分成一些数字，问我们这些数字组最大的是多少，对结果取模？

思路：首先可以明确，分成的这几个数一定是互质的。为什么呢？假设有两个数不互质，那么他们的里面势必会少乘一个他们俩的，这样肯定不如都是互质的优。那么接下来，因为都是素数，那么我们可以先把素数预处理出来，然后用这些数填满，求填满时最大的。

很神奇的事情发生了，我们发现，是不是像我们有一个容量为的背包，有个物品，每个物品的体积是，可以取无限次。

对滴，是完全背包，那么接下来就可以开始写啦。

但是！这个时候我们又遇到一个问题，结果是要取模的，但是对于取模后的数我们是没有办法比大小的，中间步骤不取模又会炸，怎么办嘞？我们考虑用来帮忙。

若$ab<cd则有log^a+log^b < log^c+log^d$

因为在库函数里面是默认以为底的，单调递增，那么我们的相对顺序没有变，而缩小了数字本身的大小，达到不会炸又可以比较大小的效果。

那么通过以上，问题解决。

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
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;
const int N =2e4+10;
bool is_pri[N];
int pri[N];
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-1; i++)
	{
		if (is_pri[i])
			pri[++cnt] = i;
		for (int j = 1; j <= cnt && i * pri[j] <= n-1; j++)
		{
			is_pri[i * pri[j]] = false;
			if (i % pri[j] == 0)break;            
		}
	}
}

ll n,mod;
double dp[N];
ll ans[N];
int main()
{
	init(N);
	while(cin>>n>>mod)
	{
		for(int i = 0;i<=n;i++)
			dp[i] = 0,ans[i] = 1;
		for(ll i = 1;i<=cnt&&pri[i]<=n;i++)//枚举物品
		{
			for(ll j = n;j>=pri[i];j--)//枚举体积
			{
				for(ll k = 1,now = pri[i];now<=j;now*=pri[i],k++)//枚举拿多少个(素数幂次)
				{
					//取模了无法比大小,用log
					if(now<=j&&dp[j-now]+log(now*1.0)>dp[j])
					{
						dp[j] = dp[j-now]+log(now*1.0);
						ans[j] = ans[j-now]*now%mod;
						//cout<<dp[j]<<endl;
					}
				}
			}
		}
		cout<<ans[n]%mod<<endl;
	}
	return 0;
}

4.Benefit 质因数分解(唯一分解定理)

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
// 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;
}

5.P1072 Hankson 的趣味题 推柿子+质因数分解

思路：因为

我们知道，对于可以转化为：。

那么我们对原式转化：，那么

于是：,再用我们的公式变成：,即：

那么我们有：

我们发现，能整除，且是的倍数，那么我们只需要枚举的因子就可以了，满足条件的加入答案。时间复杂度:

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        ll a0,a1,b0,b1;
        cin>>a0>>a1>>b0>>b1;
        
        ll ans = 0;
        ll n = sqrt(b1);
        for(ll i = 1;i <= n; i++)
        {
            if(b1%i==0){
                if(i%a1==0&&__gcd(b1/b0,b1/i)==1&&__gcd(i/a1,a0/a1)==1)ans++;
                if(i!=b1/i)
                    if((b1/i)%a1==0&&__gcd(b1/b0,b1/(b1/i))==1&&__gcd((b1/i)/a1,a0/a1)==1)ans++;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

6.P5535 【XR-3】小道消息 GCD

思路：如果是素数，那么如果区间含有的倍数肯定不能被到达。那么，如果，那么至少要次，否则次。否则的话肯定需要次。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

bool is_prime(ll x)
{
    for(ll i = 2; i <= x/i; i++)
    {
        if(x % i == 0){
            return false;
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll n,k;
    cin>>n>>k;
    n++,k++;
    int ans = 0;
    if(is_prime(k))
    {
         int left = n/k;
         if(left-1==0)ans = 1;
         else ans = 2; 
    }else{
            int left = n-(n/2);
            if(left==0)ans = 1;
            else ans = 2;
    }
    cout<<ans<<"\n";

    return 0;
}

7.P6767 Roses 贪心+GCD

思路：我们先贪心的考虑一下这个问题。

对于第一家花店每朵花的单价是，对于第二家单价是

通分一下就有：和

那么为了后面好枚举，我们假设,即第一家更优惠。

那么初始的答案就是

然后我们去枚举其中的朵在第二家买。

如果考虑买束朵的方案，我们要从枚举到，最多要次，飞了。

其实我们的枚举的上限是。

为什么呢？

如果,那么

因为

于是：,即买束方案不如买束朵方案。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll ceildiv(ll a, ll b)
{
    if(a<0)return 0;
    if(a % b == 0)  return a / b;
    else if(a > 0)  return a / b + 1;
    else return a / b;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll N,A,B,C,D;
    cin>>N>>A>>B>>C>>D;
    if(A*D<B*C){
        swap(A,C);
        swap(B,D);
    }
    int k = A/__gcd(A,C);
    //Cx = Ay
    //那么买x朵C可以用买y朵A代替,这样性价比更高
    ll ans = ceildiv(N,A)*B;
    for(int i = 1;i <= 1e5; i++)
        ans = min(ans,i*D+ceildiv(N-i*C,A)*B);
    cout<<ans<<"\n";
    return 0;
}

8.P1414 又是毕业季II 因数分解+贪心

思路：要选个人，他们的最大。我们分解因数，统计每种因数出现次数。从大的开始枚举，如果当前因数出现次数且又是最大的，那一定可以选出个是当前能选的里面最大的。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int a[N],c[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    int mx = 0;
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i];
        if(a[i]>mx)mx = a[i];
        int t = a[i];
        for(int j = 1; j <= t/j; j++)
        {
            if(t % j == 0)
            {
                c[j]++;
                if(j != t/j)c[t/j]++;
            }
        }
    }

    for(int i = 1;i <= n; i++)
    {
        while(c[mx]<i)mx--;
        cout<<mx<<"\n";
    }
    return 0;
}

9.P8926 「GMOI R1-T3」Number Pair 线性筛+GCD

思路：

那么：

于是

又因为

那么，且

那么我们去对质因数分解，把不同的质因数分配给，种类数就是，其中的质因数种类数。

那么答案就是

注意本题卡常，注意优化。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e8 + 10;
int tot, pr[N];
bool p[N];
void prime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!p[i])    p[i] = i, pr[++tot] = i; 
        for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
            if(1ll * pr[j]*i>1e8)break;
            p[pr[j] * i] = pr[j];
            if(p[i] == pr[j])   break;
        }
    }
}

ll qmi(ll a, ll b, ll mod)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    prime(100000000);
    //cout<<"tot = "<<tot<<"\n";
    while(t--)
    {
        ll k,P,Q;
        cin>>k>>P>>Q;
        int s = 0;
        for(int i = 1; i <= tot&& k!=1 ;i++)
        {
            if(1ll * pr[i] * pr[i] > k)break;
            if(k % pr[i]==0)
            {
                s++;
                while(k % pr[i]==0)k/=pr[i];
            }
        }
        if(k>1)s++;
        cout<<qmi(2,s,mod)*((Q-P+1ll)%mod)%mod<<"\n";
    }
    return 0;
}

10.[P6659 POI 2019] Najmniejsza wspólna wielokrotność

思路：二分+gcd

答案可以分为长度为的和长度的。

如果长度为，考虑直接二分答案。

因为，那么长度位数不超过，那么对于长度的可以考虑暴力枚举左端点，然后扩展右端点，用记录答案。

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
75
76
77
78
79
80
81
82
83
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const ll inf = 1e18;
ll lcm(ll a,ll b)
{
    return a/__gcd(a,b)*b;
}
struct node
{
    ll l,r;
};
map<ll,node>mp;

node find(ll x)
{
    ll l = 1,r = 1e9;
    while(l<=r)
    {
        ll mid = (l+r)>>1;
        if(mid*(mid+1)>x)r = mid-1;
        else if(mid*(mid+1)<x)l = mid+1;
        else return node({mid,mid+1});
    }
    return (node){0,0};
}

void init(ll n)
{
    for(ll l = 1; l <= n; l++)
    {
        ll res = l*(l+1);
        for(ll r = l+2;;r++)
        {
            res/=__gcd(res,r);
            if(res>inf/r)break;
            res *= r;
            if(!mp.count(res))mp[res] = (node){l,r};
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin>>T;
    ll maxn = 1e7+10;
    init(maxn);
    //19!<1e18<20!
    while(T--)
    {
        ll m;
        cin>>m;
        auto ans1 = find(m),ans2 = mp[m];
        if(!ans1.l&&!ans2.l)
        {
            cout<<"NIE\n";
            continue;
        }
        else if(!ans1.l&&ans2.l)
        {
            cout<<ans2.l<<" "<<ans2.r<<"\n";
        }
        else if(ans1.l&&!ans2.l)
        {
            cout<<ans1.l<<" "<<ans1.r<<"\n";
        }
        else{
            if(ans1.l<ans2.l)cout<<ans1.l<<" "<<ans1.r<<"\n";
            else if(ans1.l>ans2.l)cout<<ans2.l<<" "<<ans2.r<<"\n";
            else{
                if(ans1.r<ans2.r)cout<<ans1.l<<" "<<ans1.r<<"\n";
                else cout<<ans2.l<<" "<<ans2.r<<"\n";
            }
        }
    }
    return 0;
}

11.[AGC022B] GCD Sequence 构造+GCD

思路：首先要满足互质，这个很容易满足，我们只要包含即可。

如果，由于，那么和为，第一组的三个数就是。接下来构造两个为一组，和还是为，如果或或，那么答案就是了。这样和就是的倍数，保证了不为。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    cout<<"2 3 29995 ";
    if(n%2==0)cout<<"30000 ",n--;
    n-=3;
    n/=2;
    for(int i = 6;n;i++)
    {
        if(i%2==0||i%3==0||i%5==0)
        {
            n--;
            cout<<i<<" "<<30000-i<<" ";
        }
    }
    cout<<"\n";
    return 0;
}

12.P2651 添加括号III

题意：现在给出一个表达式，形如 。

如果直接计算，就是一个个除过去，比如 。

然而小看到一个分数感觉很不舒服，希望通过添加一些括号使其变成一个整数。一种可行的办法是 。

现在给出这个表达式，求问是否可以通过添加一些括号改变运算顺序使其成为一个整数。

思路：首先一定是分子，一定是分母，我们要使得尽可能是整数，我们可以考虑把之后的全放分母。这个好办：

这题不用高精度，只需要每次对除以和其他每个数的,只要最后，那么就能整除啦。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];

        a[2]/=__gcd(a[1],a[2]);
        for(int i = 3;i <= n; i++)
            a[2]/=__gcd(a[2],a[i]);
        if(a[2]==1)cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

13. P2118 比例简化

题意：在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 人，反对的有 人，那么赞同与反对的比例可以简单的记为 。

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 ，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数 ，反对人数 ，以及一个上限 ，请你将 比 化简为 比 ，要求在 和 均不大于 且 和 互质（两个整数的最大公约数是 ）的前提下， 且 的值尽可能小。

思路：上界是，考虑枚举，取满足条件的且差最小的。为了避免误差，交叉相乘比较。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll a,b,l;
    cin>>a>>b>>l;
    ll ansa = 100,ansb = 1;
    for(int a1 = l; a1 >= 1; a1--)
    {
        for(int b1 = l; b1 >= 1; b1--)
        {
            //a1/b1>=a/b
            if(a1*b>=b1*a)
            {
                if(__gcd(a1,b1)==1)
                {
                    if(ansa*b1>ansb*a1)
                    {
                        ansa = a1,ansb = b1;
                    }
                }
            }
        }
    }
    cout<<ansa<<" "<<ansb<<"\n";
    return 0;
}

P4160 生日快乐 搜索+GCD

题意：windy 的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 和 的矩形蛋糕。

现在包括 windy，一共有 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。

windy 主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。

这样，要切成 块蛋糕，windy 必须切 次。

为了使得每块蛋糕看起来漂亮，我们要求 块蛋糕的长边与短边的比值的最大值最小。

你能帮助 windy 求出这个比值么？

思路：由于要把大小的矩形切成块，那么最终切好的每一块的大小就是

对于,最多被切成。对于,最多被切成。那么我们每次一定切的的一定是或者的倍数。

于是我们开始搜索，每次考虑切长或者宽，在分出的两块中选出比值的最大值，去更新答案。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
double x,y,n;

double dfs(double x,double y,double n)
{
    if(n==1.0)
        return max(x,y)/min(y,x);

    double minx = x/n,miny = y/n,ans = 1e18;
    for(double i = 1.0; i<= n/2.0;i+=1.0)
    {
        double t1 = max(dfs(minx*i,y,i),dfs(x-minx*i,y,n-i));
        double t2 = max(dfs(x,miny*i,i),dfs(x,y-miny*i,n-i));
        ans = min(ans,min(t1,t2));
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    cin>>x>>y>>n;
    printf("%.6lf\n",dfs(x,y,n));
    return 0;
}

[hdu 5970]GCD+循环节

[hdu 5584]LCM问题

[洛谷 P2568 ]GCD + 莫比乌斯反演

[洛谷 P2398]GCD求和

[洛谷 P1890]询问区间内的GCD

  • Title: GCD&LCM practice
  • Author: Nannan
  • Created at : 2023-11-06 17:41:00
  • Updated at : 2024-09-30 19:22:52
  • Link: https://redefine.ohevan.com/2023/11/06/GCD&LCM practice/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
GCD&LCM practice
  1. GCD&LCM practice
    1. 1.GCD and LCM - HDU 4497 GCD和LCM性质
    2. 2.hide handkerchief - HDU 2104 互素判定
    3. 3.Least common multiple - HDU 3092 GCD+完全背包
    4. 4.Benefit 质因数分解(唯一分解定理)
    5. 5.P1072 Hankson 的趣味题 推柿子+质因数分解
    6. 6.P5535 【XR-3】小道消息 GCD
    7. 7.P6767 Roses 贪心+GCD
    8. 8.P1414 又是毕业季II 因数分解+贪心
    9. 9.P8926 「GMOI R1-T3」Number Pair 线性筛+GCD
    10. 10.[P6659 POI 2019] Najmniejsza wspólna wielokrotność
    11. 11.[AGC022B] GCD Sequence 构造+GCD
    12. 12.P2651 添加括号III
    13. 13. P2118 比例简化
    14. P4160 生日快乐 搜索+GCD
    15. [hdu 5970]GCD+循环节
    16. [hdu 5584]LCM问题
    17. [洛谷 P2568 ]GCD + 莫比乌斯反演
    18. [洛谷 P2398]GCD求和
    19. [洛谷 P1890]询问区间内的GCD