E. Border

题目链接

Codeforces Round #499 (Div. 2)--E. Border

题解

高档题。题意大概是对于n个数与k进制,求出a1b1+a2b2+...+an*bn模k所得的可能的数,其中ai为给定的数,bi为任意非负整数。

将所有给定的数字取最大公约数即为我们所要考虑的最小的单元,假设所得的数为a,则ab(b为任意非负整数)模k可能的数的数量为k/gcd(a,k),即只要依次标记并输出0a,2a,...,(k/gcd(a,k)-1)a即可。

代码

#include <cstdio>
#include <iostream>
using namespace std;

int n, k;
int a, q1;
bool output[100005];

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    cin >> n >> k;
    scanf("%d", &a);
    n--;
    while (n--) {
        scanf("%d", &q1);
        a = gcd(a, q1%k);
    }

    q1 = 0;
    for (int i = 1; i <= k / gcd(a, k); i++) {
        q1 += a;
        output[q1%k] = true;
    }

    cout << k / gcd(a, k) << endl;
    for (int i = 0; i < k; i++) {
        if (output[i])cout << i << ' ';
    }
}

标签: number theory

添加新评论