GCD

· · 个人记录

今天学 GCD,希望明天不要了奥,因为数学不好...

~不过我很骄傲,这可能是因为跟我的家教有关吧~

不知道为什么打不出句号啊.?

没关系,~I don't car.~

P8469 [Aya Round 1 D] 文文的数学游戏

第一问: 我们不妨把数组里面的数都设成 a 数组中最小的,那么第一问就是 \operatorname{min\{a_i}\}.

第二问: 因为当前这个位置能选择的数都只能是 gcd 的倍数,所以可选择的个数有 a_i / gcd 个,在使用乘法原理即可.

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

#define int long long
int n;
int a[100005];
int minn = 1e9;
int sum = 1; 

const int MOD = 1e9 + 7;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        minn = min (minn, a[i]);
    }
    cout << minn << ' ';
    for (int i = 1; i <= n; i ++)
    {
        sum = (sum * (a[i] / minn)) % MOD;
    }
    cout << sum % MOD;
    return 0;
}

P2965 [USACO09NOV] The Grand Farm-off S

这题就是模法公式,很乱,要写的工整点,不然就会像 2b2b2bbb 一样改不出来.

加法公式:

int ADD (int a, int b, int mod)
{
    return (a % mod + b % mod) % mod;
}

乘法公式:

int MUL (int a, int b, int mod)
{
    return ((a % mod) * (b % mod)) % mod;
}

剩下的没什么好讲的

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

#define int long long
struct node
{
    int w, u;
}A[1500015];

int n, a, b, c, d, e, f, g, h, m;

bool cmp (node a, node b)
{
    return ((a.u == b.u) ? (a.w < b.w) : (a.u > b.u));
}

int MUL (int a, int b, int mod)
{
    return ((a % mod) * (b % mod)) % mod;
}

int add (int a, int b, int mod)
{
    return (a % mod + b % mod) % mod;
}

int calc(int x, int y, int mod)
{
    int cnt = 1;
    while (y --)
    {
        cnt = MUL(cnt, x, mod);
    }
    return cnt;
}

signed main()
{
    cin >> n >> a >> b >> c >> d >> e >> f >> g >> h >> m;
    for (int i = 0; i < 3 * n; i ++)
    {
        A[i + 1].w = add(MUL(a, calc(i, 5, d), d), add(MUL(b, calc(i, 2, d), d), c, d), d);
        A[i + 1].u = add(MUL(e, calc(i, 5, h), h), add(MUL(f, calc(i, 3, h), h), g, h), h);
//      cout << A[i + 1].w <<  ' ' << A[i + 1].u << endl;
    }
    sort (A + 1, A + 1 + 3 * n, cmp);
    int sum = 0;
    for (int i = 1; i <= n; i ++)
        sum = add(sum, A[i].w, m);
    cout << sum;
    return 0;
}

P10030 「Cfz Round 3」Change

题目保证 p 是质数,所以我们得知:每一个 x 都会被遍历到,因为 p 是质数,而你是永远到不了 p 的,因为会取模.

而我们发现,当发生 b=0 情况时,是永远都到不了的,因为 x 初始为 0,0 不管怎么乘都是 0,而加法也到不了大于等于 1 的整数,所以这种情况无解.

反之其他情况都有解.

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

#define int long long
int n;
int a[2000005];

signed main()
{
    cin >> n;
    while (n --)
    {
        int p, a, b, c;
        cin >> p >> a >> b >> c;
        if (b == 0 and c != 0)
            puts("nO");
        else
            puts("yeS");
    }
    return 0;
}

P10183 [YDOI R1] Running

首先我们先要知道一种无解的情况,即数组中有奇数,会被同学拉爆.

其他的,为了保证时间是偶数,我们可以把它除以 2,而为了保证速度最大且需要时刻保持能整除,所以是求这些的 \operatorname{gcd}.

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

#define int long long
int n;
int a[2000005];
int Gcd

;signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if (a[i] % 2 == 1)
        {
            cout << -1;
            return 0;
        }
    }
    Gcd = a[1] / 2;
    for (int i = 1; i <= n; i++)
    {
        Gcd = __gcd(Gcd, a[i] / 2);
    }
        cout << Gcd;
    return 0;
}