This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=1e5+7;
vector<int> adj[N];
int p[N];
int P[30][N];
int ans[30][N];
int L[N];
int n,m,q;
int gcd(int a,int b){
if(b==0) {
return a;
}
return gcd(b,a%b);
}
void dfs(int u,int p){
L[u]=L[p]+1;
P[0][u]=p;
ans[0][u]=gcd(u,p);
for(int v:adj[u]) {
if(v==p) continue;
dfs(v,u);
}
}
void do_stuff(){
for(int i=1; i<28; i++) {
for(int j=1; j<=n; j++) {
P[i][j]=P[i-1][P[i-1][j]];
ans[i][j]=min(ans[i-1][P[i-1][j]],ans[i-1][j]);
}
}
}
void init(){
for(int i=1; i<=n; i++) {
p[i]=i;
}
}
int find(int x){
return (p[x]==x) ? x : p[x]=find(p[x]);
}
bool merge(int a,int b){
int u=find(a);
int v=find(b);
if(u==v) return 0;
p[u]=v;
return 1;
}
int lca(int a,int b){
int mx=1e9;
if(L[b]<L[a]) {
swap(a,b);
}
int d=L[b]-L[a];
for(int i=28; i>=0; i--) {
if((1<<i)&d) {
mx=min(mx,ans[i][b]);
//cout<<i<<" "<<ans[i][b]<<endl;
b=P[i][b];
}
}
if(a==b) {
return mx;
}
for(int i=28; i>=0; i--) {
if(P[i][a]!=P[i][b]) {
mx=min(mx,ans[i][a]);
mx=min(mx,ans[i][b]);
a=P[i][a];
b=P[i][b];
}
}
mx=min({mx,ans[0][a],ans[0][b]});
return mx;
}
int main()
{
ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m>>q;
init();
for(int i=m; i>=1; i--) {
for(int j=i+i; j<=n; j+=i) {
if(merge(i,j)) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
dfs(1,0);
do_stuff();
while(q--) {
int a,b;
cin>>a>>b;
int ans=lca(a,b);
assert(ans!=1e9);
cout<<m-ans+1<<endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |