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

問題ページ
Problem - E - Codeforces

考えたこと

• k進数の下一桁はkで割った余りに等しい
• a[i] mod k を取っておいてよさそう
• dp[i番目][金額]=(bool)とかしたいけど10^10なので無理
• a[i]がkと互いに素なら0～k-1まで全て取りうる
• a[i]がkと互いに素でない場合を考える
• a[i]の倍数を取りえる
• a[i]の倍数を全列挙していくコードを書いても調和数的に計算量は間に合いそう
• 書いて出すと落ちる
  -----バーチャルコンテスト終わり-----
• 冷静に考えてa[i]がkと互いに素でない場合についてa[i]の倍数だけじゃだめ
• n=2,k=20,a={4,5} とかだめ
• i番目の紙幣を使う枚数をx[i]とすると金額は sum(a[i]x[i]) となる
• ベズーの補題より sum(a[i]x[i]) は gcd(a[i]) の倍数となる
• よって gcd(a[i])の倍数 mod k を列挙すればよい

ベズーの補題を覚えた、これ知らない状態でgcd取るの思いつく気がしない

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, k;
  cin >> n >> k;
  VI a(n);
  REP(i, n) cin >> a[i];

  int g = 0;
  REP(i, n) g = __gcd(g, a[i]);

  set<int> st;
  REP(i, k) st.insert((g*i)%k);

  cout << st.size() << endl;
  for(auto i: st) cout << i << " ";
  cout << endl;

  return 0;
}