3 min
补题 | ABC482F
题目#
Problem Statement#
You are given positive integers and . For each , solve the following problem.
- Determine whether there exists a positive integer satisfying the following condition, and if it exists, find the minimum such .
- There exists a positive divisor of such that .
思路#
的情况不难想到分解素因数,考虑写作 ,若 ,则不可行,否则考虑 即可。
沿着这个方向考虑,如果我们得到了 的情况,那么 也是可以容易得到的。显然: 可以表示,当且仅当从 开始,通过反复乘上某个 并对 取模,可以达到 .
因此,穷尽上述操作能够到达的所有余数后,未被到达的余数恰好就是无解的情况。
写成转移:
枚举 是困难的,不妨将 写作一个包含重复因子的序列,对序列中每一项,考虑是否加入,如果加入就进行一次如上的转移。这样,一整轮恰好对应乘上一个 的约数。因此可以建立状态 ,表示当前处理位置和余数;每条边处理一个因子,位置循环前进。从 做普通 BFS,到达 的最短距离一定是 的倍数,除以 就得到最小轮数。
代码#
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
int M;
cin >> N >> M;
vector<int> factors;
ll n = N;
for (ll p = 2; p <= n / p; ++p) {
while (n % p == 0) {
factors.push_back(p % M);
n /= p;
}
}
if (n > 1) {
factors.push_back(n % M);
}
int start = 1 % M;
int L = factors.size();
if (L == 0) {
for (int k = 0; k < M; ++k) {
cout << (k == start ? 1 : -1) << '\n';
}
return 0;
}
vector<int> dist(L * M, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int id = q.front();
q.pop();
int i = id / M;
int r = id % M;
int next_i = (i + 1) % L;
int base = next_i * M;
int to = base + r;
if (dist[to] == -1) {
dist[to] = dist[id] + 1;
q.push(to);
}
int next_r = 1LL * r * factors[i] % M;
to = base + next_r;
if (dist[to] == -1) {
dist[to] = dist[id] + 1;
q.push(to);
}
}
for (int k = 0; k < M; ++k) {
if (dist[k] == -1) {
cout << -1 << "\n";
} else {
cout << max(1, dist[k] / L) << "\n";
}
}
return 0;
}cpp