General
 
 
# 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
→ Source
#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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details