GCD相关（不定期更新）

本博文总结了有关gcd知识的题目

个人心得：

题目1：

题目链接：科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛 A-张老师和菜哭武的游戏

分析：

不定方程：ax+by=c。该方程有解当且仅当c=kgcd(a, b)，也就是c是gcd(a, b)的倍数。

很显然（其实不怎么显然）衍生出的一系列的数c都是起始两个数的线性组合。故c一定是gcd的倍数。又因为只要c = kgcd(a, b)， 则c一定是由a，b组合得到的。所以只需要求出1-n有多少gcd(a, b)的倍数，做法就是用n除以gcd(a, b)，看看结果的奇偶性。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
 
ll gcd(ll a, ll b)
{
    return !b ? a : gcd(b, a % b);
}
 
int main()
{
    int t; cin >> t;
    while(t--)
    {
        ll n, a, b; cin >> n >> a >> b;
        ll gg = gcd(a, b);
        if(n / gg % 2) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}
           

题目2：

题目链接：青蛙的约会 POJ - 1061

分析：

exgcd模板题。重点是如何处理答案为负数的情况。

代码：

#include <iostream>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;

void exgcd(ll a, ll b, ll &gcd, ll &x, ll &y)
{
    if(!b) gcd = a, x = 1, y = 0;
    else exgcd(b, a % b, gcd, y, x), y -= x * (a / b);
}

int main()
{
    ll x, y, m, n, l; cin >> x >> y >> m >> n >> l;
    ll a, t, b, k, c, gcd;
    a = n - m, b = l, c = x - y;
    exgcd(a, b, gcd, t, k);
    if(c % gcd)
    {
        cout << "Impossible" << endl;
        return 0;
    }
    t *= (c / gcd);
    ll step = b / gcd;
    cout << (t % step + step) % step << endl;
}
           

题目3：

题目链接：GCD XOR UVA - 12716

分析：

本题的主要想法就是找到一个沟通gcd（a,b）和a^b的桥梁

1)a^b≥a-b

2)a-b≥gcd(a,b)。

由九章算术·更相减损术可得gcd(a,b)=gcd(a,a-b)=gcd(b,a-b)。显然a-b≥gcd(a,a-b)，得证

我们现在已知gcd（a,b）=a-b，根据夹逼法，a^b=a-b=gcd(a,b)=gcd(a,a-b)

换言之，a^b等于a-b，还有取等前提a-b是a的因子

因此我们枚举a-b，求得它的所有倍数，再判断a-b=a^b是否成立。时间复杂度O(N+N/2+N/3+……+N/N)=O(N logN)

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 3e7 + 10;
const int inf = 0x3f3f3f3f;
ll v[maxn];

void init()
{
    for(int i = 1; i <= 3e7; i++)
        for(int j = 2 * i; j <= 3e7; j += i)
        {
            ll a = j, b = j - i;
            if(a - b == (a ^ b))
                v[a]++;
        }
    for(int i = 1; i <= 3e7; i++) v[i] += v[i - 1];
}
int main()
{
    init();
    int t; cin >> t;
    int cases = 0;
    while(t--)
    {
        ll n; cin >> n;
        printf("Case %d: %lld\n", ++cases, v[n]);
    }
}
           

题目四：C Looooops POJ - 2115

题目链接：C Looooops

分析：

1、先将同余方程转换为二元不定方程

2、用exgcd求得一组解

3、求得最小整数解

4、注意：ll k = 1ll << 32中的1一定要是ll，不然会wa！

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;

void exgcd(ll a, ll b, ll &gcd, ll &x, ll &y)
{
    if(!b) gcd = a, x = 1, y = 0;
    else exgcd(b, a % b, gcd, y, x), y -= x * (a / b);
}

int main()
{
    ll a, b, c, k;
    while(cin >> a >> b >> c >> k && (a || b || c || k))
    {
        ll mod = 1ll << k;
        ll gcdd, x, y;
        exgcd(c, mod, gcdd, x, y);
        if((b - a) % gcdd) cout << "FOREVER" << endl;
        else
        {
            x *= (b - a) / gcdd;
            ll cnt = (x % (mod / gcdd) + mod / gcdd) % (mod / gcdd);
            cout << cnt << endl;
        }
        
    }
}