190227模拟
题目描述给定一张 N 个点的有向图，点 i 到点 j 有一条长度为 i/gcd(i,j) 的边.
有个 Q 询问，每个询问包含两个数 x, y，求从点 x 出发到点 y 的最短距离。
输入格式第一行包含两个用空格隔开的整数 N Q。
接下来 Q 行，每行两个整数 x 和 y。
输出格式
输出 Q 行整数，表示从点 x 出发到点 y 的最短距离。
提示与说明对于30%的数据，1≤N≤100。
对于70%的数据，1≤N≤10^5。
对于100%的数据，1≤x,y≤N≤10^7, Q≤ 10^5。
虽然是求最短路，但这显然是一道数论题。
通过打表找规律，发现答案就是(x/gcd(x,y))的质因数之和。
筛质数的时候，每次把它被整除的最小质因数记下来....反正看代码吧
有个写了个√n的dalao的写法我也不懂，反正我一个一个质数枚举都会t
代码如下
#include<cstdio>
#include<iostream>
#define MogeKo qwq
using namespace std;
const int maxn = 1e7+;
int prime[maxn],p[maxn];
int n,q,x,y,cnt;
bool vis[maxn]; int gcd(int a,int b) {
if(b==)return a;
return gcd(b,a%b);
} int solve(int x) {
int sum = ;
while(x!=) {
sum += p[x];
x /= p[x];
}
return sum;
} void Prime(int N) {
for(int i=; i <= N; i++) {
if(!vis[i]) {
prime[++cnt]=i;
p[i] = i;
}
for(int j=; j<=cnt && prime[j]*i <= N; j++) {
vis[prime[j]*i] = true;
p[prime[j]*i] = prime[j];
if(i%prime[j]==)break;
}
}
} int main() {
scanf("%d%d",&n,&q);
Prime(n);
while(q--) {
scanf("%d%d",&x,&y);
if(x==y) {
printf("0\n");
continue;
}
x /= gcd(x,y);
int ans = solve(x);
if(!ans)ans = ;
printf("%d\n",ans);
}
return ;
}
模拟Prime写崩了QAQQQQ（无能狂怒）
19/3/30
我突然想起来这个好像可以用欧拉函数来做...
不用求素数表，直接根据唯一分解定理从2到n枚举就行了?不知道对不对
int euler(int n){
int sum = ;
for(int i = ;i*i <= n;i++)
while(n%i==){
sum += i;
n /= i;
}
if(n>) sum += n;
return sum;
}