最初誤読して、「何度でもスタート地点にワープして戻っても良い」というバージョンの問題を解いていた。
問題概要
個の整数
と 2 以上の整数
が与えられる。
頂点からなる以下のような有向グラフであって、頂点 1 を始点として、頂点
をすべて訪れるようなウォークが存在するかどうかを判定せよ。
- 各頂点
に対して、
となるような
が存在するとき、有向辺
が張られている
制約
解法 (1):純粋にグラフの問題として解く
想定解法はこちらだった。
- 強連結成分分解する (各連結成分内では自由に行き来できる)
- 頂点 1 を含む連結成分から各連結成分への最長路 (DAG なので DP でできる) を求める
- その値が、DAG の辺数に等しければ Yes、そうでなければ No
計算量は 。
解法 (2):整数論的考察する
最初誤読して、「個数制限なしナップサック問題」かと勘違いしてしまった。しかし、一度頂点を出発したら、引き返せない設定だと気づいた。
さて、そうとなれば を素因数分解したときに、複数の素因数を持つ場合はダメ。たとえば
としたとき、
- 頂点 2 に訪れるよりも先に頂点 3 を訪れてしまったならば、それ以降は 3 の倍数にしかならないので、頂点 2 へ行くのは不可能
- 頂点 3 に訪れるよりも先に頂点 2 を訪れてしまったならば、それ以降は 2 の倍数にしかならないので、頂点 3 へ行くのは不可能
という感じだ。一般に、M が相異なる素数 でともに割り切れるとき、頂点
に両方とも行くことは不可能なのだ。
M が素数べきのとき
こうして問題は、 が素数べきの場合のみに限られた。この場合は次のようになる。
と互いに素な整数をすべて作れなければ明らかにダメ
としたとき、ある
が存在して、
でなければダメ (これを
とする)
ということが言える。逆にこれらを満たせばすべて作ることができる。具体的には次のようにする。
- まず
と互いに素な整数をすべて作る (1 に戻ってこれる)、そして頂点 1 に戻ってくる
- 頂点 1 から、頂点
へと遷移する。ここから、ふたたび
と互いに素な整数を順にかけていく。こうすることで、
との最大公約数が
であるような頂点をすべて行き渡る。そして頂点
に戻ってくる
- 頂点
から、頂点
へと遷移する。ここから同様にして、
との最大公約数が
であるような頂点をすべて行き渡ることができる。そして頂点
に戻ってくる
- 以下同様
M と互いに素な整数をすべて作れるか
との最大公約数が
であるような元が存在するかどうかを判定するのは簡単。残りは、
と互いに素な整数をすべて作れるかどうかを判定する部分。
実はこうなったらもうナップサック問題でやってもいい。なぜなら、 と互いに素な整数
に対してはオイラーの定理から
が成立するので、 を何回もかけていたらいつかは 1 に戻るのだ。よって、
と互いに素な整数をかけているうちは、いつでも 1 に戻ってこれるので、ナップサック問題と考えて OK。具体的には
と互いに素であるような各
に対して、その冪乗のとりうる値を求める
- それらを併合したものを作る (高々
個になる)
- それらでナップサック問題を解く
という風にした。さらに、
のうち、
と互いに素な整数を選んでかけることで
と互いに素な剰余をすべて作れる
との最大公約数が
であるような元が存在する
ということと
から選んでかけることで
の剰余をすべて作れる
ということは同値なので、まとめてやった。計算量は 。
#include <bits/stdc++.h> using namespace std; vector<pair<long long, long long> > prime_factorize(long long n) { vector<pair<long long, long long> > res; for (long long p = 2; p * p <= n; ++p) { if (n % p != 0) continue; int num = 0; while (n % p == 0) { ++num; n /= p; } res.push_back(make_pair(p, num)); } if (n != 1) res.push_back(make_pair(n, 1)); return res; } bool solve() { int N, M; cin >> N >> M; vector<long long> a(N); for (int i = 0; i < N; ++i) cin >> a[i], a[i] %= M; // 素因数が複数個あったらダメ auto pf = prime_factorize(M); if (pf.size() >= 2) return false; // a[i] の冪乗でできるものを列挙 set<long long> se; for (int i = 0; i < N; ++i) { set<long long> tmp; long long cur = a[i]; while (!tmp.count(cur)) { tmp.insert(cur); cur = (cur * a[i]) % M; } for (auto it : tmp) se.insert(it); } // ナップサック vector<bool> dp(M, false), ndp; dp[1] = true; for (auto it : se) { ndp.assign(M, false); for (long long j = 0; j < M; ++j) { if (!dp[j]) continue; ndp[j] = true; ndp[(j * it) % M] = true; } swap(dp, ndp); } for (int j = 0; j < M; ++j) if (!dp[j]) return false; return true; } int main() { if (solve()) cout << "Yes" << endl; else cout << "No" << endl; }