牛客 计数器

题意：

计算器初始值为0．每次操作可把计算器的值加上$a_1, a_2, ....., a_n$中的任意一个整数，操作次数不限（可以为0次），问计算器的值对ｍ取模有多少种可能

思路：

相当于求$n + 1$个整数的最大公约数，得$a_1x_1 + a_2x_2 + ... + a_nx_n + km = d$

则计算器值对ｍ取模有ｍ/d种可能

Code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

int n, m;
int x;

int main(){
    cin >> n >> m;
    
    int g = m;
    for(int i = 0; i < n; i ++){
        cin >> x;
        g = __gcd(g, x);
    }
    cout << m / g << endl;
    
    return 0;
}