2022“杭电杯”中国大学生算法设计超级联赛(9)1008 Shortest Path in GCD Graph(个人题解)
HDU-7240: Shortest Path in GCD Graph
解题思路:考虑到每条边的权值为GCD(i,j),那么对于任何的i,j点来说。
1、若GCD(i,j)!=1时,i,j点必定能够分别和1节点相连形成一条边权为1的边(合起来长度便为2),因此,最小的连接长度就是2。我们只需要计算出1-n范围内与i,j互质的点k的数量便是答案。为了求出与i,j互质的数的数量,我们可以分别处理出i和j的质因数,运用set去重,再将剩余的质因数进行容斥操作(此处暂不介绍容斥,请自行观看),
注意,在计算过程中,若GCD(i,j)=2,也需要在最终答案中+1计算进去。
2、若GCD(i,j)==1时,那么i-j的这条边路径长度为1便是最小的,并且不会有其他相同长度的路径。直接输出1 1即可。
注:该题卡常,必须用素数筛优化分解质因数并且不能使用二进制的容斥,只能用dfs版的方式求容斥(直接裂开)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e7 + 7;
const int mod = 998244353;
const int inf = 1e18 + 9;
int t, n, m, x,k,q,a,b,cnt;
int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int GCD(int a, int b)
{
if (b == 0)return a;
return GCD(b, a % b);
}
//素数筛优化分解质因数
int prime[maxn];//记录所有素数的数组 prime[0]存放范围内素数数量
bool vis[maxn];//记录所有数,并将其标记合数为1,素数为0
void Prime(int n) {
memset(vis, 0, sizeof(vis));//初始化全为素数
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && i * prime[j] <= n; j++) {
vis[i * prime[j]] = 1;//标记合数为1
if (i % prime[j] == 0)break;
}
}
}
int ans;
vector<int>p;
set<int>se;//用来筛去相同的质因数
//分解质因数,素数筛优化
void Divide(int m)
{
if (!vis[m]) {
se.insert(m);
return;
}
for (int i = 1; i <=prime[0] && m>1; i++){
if (m % prime[i] == 0){
se.insert(prime[i]);
while (m % prime[i] == 0) m /= prime[i];
if (m > 1 && !vis[m]){
se.insert(m);return;
}
}
}
}
//dfs版跑容斥
//1-n中与a,b互斥的元素个数
void dfs(int k, int l, int s, int a)
{
if (k == p.size()) {
if (l & 1) ans -= a / s;
else ans += a / s;
return;
}
dfs(k + 1, l, s, a);
dfs(k + 1, l + 1, s * p[k], a);
return;
}
void work(int n, int a,int b)
{
ans = 0;
p.clear();se.clear();
Divide(a);Divide(b);
for (auto x : se)p.push_back(x);
dfs(0, 0, 1, n);
}
signed main()
{
n = read(); q = read();
Prime(n);
for (int i = 0; i < q; i++) {
a = read(); b = read();
int temp = GCD(a, b);
if (temp==1)cout << 1 << " " << 1 << "\n";
else {
cout << 2 << " ";
work(n,a,b);
cout << (ans + (temp == 2 ? 1 : 0)) % mod << "\n";
}
}
return 0;
}