# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
184955390 |
Contestant:
Zoro |
1766D
- 24
|
C++17 (GCC 7-32)
|
Time limit exceeded on test 10
|
4000 ms
|
79660 KB
|
2022-12-12 18:48:59 |
2022-12-13 11:03:44 |
|
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ini(n) ll n;cin>>n
#define sti(n) string n;cin>>n
#define arri(arr,s,e) for (int i = (s); i <= (e); i++)cin>>arr[i]
#define frange(i,s,e) for (int i = (s); i <= (e); i++)
#define ff first
#define ss second
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
const ll MAX=200001;
vector<bool> primebool(10000001,true);
vector<ll> spf(10000001);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
primebool[1]=false;
spf[1]=1;
for (ll i = 2; i < 10000001; i++){
if(primebool[i]){
spf[i]=i;
for (ll j = i*i; j < 10000001; j+=i){
if(primebool[j])spf[j]=i;
primebool[j]=false;
}
}
}
while(t--){
ll n,m;
cin>>n>>m;
ll dif=m-n;
if(dif==1)cout<<-1<<endl;
else{
ll d=dif;
ll ans=INT64_MAX;
vector<int> s1;
while (d>1){
if(n%spf[d]==0){
ans=n;
break;
}
s1.push_back(spf[d]);
d/=spf[d];
}
if(ans==n){
cout<<0<<endl;
continue;
}
for(auto a:s1){
// ll a=b.ff;
ans=min(ans,((n/a)+1)*a);
}
cout<<ans-n<<endl;
}
}
return 0;
}
Click to see test details