数学一本通例题

题意

有一个密码箱,0n-1 中的某些整数是它的密码。且满足:若 ab 是它的密码,则 (a+b)\bmod n 也是它的密码(ab 可以相等)。某人试了 k 次密码,前 k-1 次都失败了,最后一次成功了。

问,该密码箱最多有多少种不同的密码。

思路

可以证明,密码集合 A 里面的数一定是形如 x, 2x, 3x\cdots 的形式(模意义下),且 x\mid a_k\land \forall i。并且如果 x\in A\gcd(x, n)\in A

做法:a_k:= \gcd(a_k, n),然后考虑 a_k 的每个因子,如果能整除 \gcd(a_i, a_k) 那就不行,遇到答案输出即可。

#include <cstdio>
#include <algorithm>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define DEC(i, a, b) for (int i = a; i >= b; --i)

typedef long long ll;

const int maxn = 250000 + 5;
ll a[maxn], k, n, tot, ans;

inline ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
inline ll max(ll a, ll b) {return a > b ? a : b;}

bool check(ll x)
{
    DEC(i, tot, 1)
        if (a[i] % x == 0)
            return false;
    return true;
}

int main()
{
    scanf("%lld %lld", &n, &k);
    FOR(i, 1, k) scanf("%lld", a + i), a[i] = gcd(a[i], n);
    std::sort(a + 1, a + k);
    tot = std::unique(a + 1, a + k) - a - 1;
    for (ll i = 1; i * i <= a[k]; ++i)
    {
        if (a[k] % i == 0)
        {
            if (check(i))
            {
                ans = n / i;
                break;
            }
            else if (check(a[k] / i))
                ans = max(n / (a[k] / i), ans);
        }
    }
    printf("%lld\n", ans);
    return 0;
}
最后修改日期: 2021年2月25日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。