【貝祖定理 && 數論】Codeforces 1011F Border

• Step1 Problem

原題

給你n個數，每個數能無限次和其他任意個數自由組合得到一個新的數，所有新的數在k進制下的最後一位有多少種情況，按升序輸出所有情況。

• Step2 Ideas:

預處理出每一個數在k進制下的最後一位的情況，然後得出他們的最大公因數，根據貝祖定理得到的最大公因數可以算出他們的在k内的所有可能組合，注意超過的部分要取模。可以發現，設某數值為a，任意個a的和在k進制下能形成的尾數為a與k的最大公因數的倍數。則找出取餘後的n個數與k的最大公因數x，則x在k内的倍數即為所有可能出現的尾數。

• Step3 Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;

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

int main()
{
    int n, k;
    cin >> n >> k;
    int t = k;
    for(int i = 1;i <= n; i++)
    {
        int x;
        cin >> x;
        t = gcd(t, x);
    }
    cout << k/t << endl;
    for(int i = 0; i*t < k; i++)
    {
        cout << i*t << ' ';
    }
    cout << endl;
    return 0;
}