59 lines
1.2 KiB
C++
59 lines
1.2 KiB
C++
/// Gheorghies Alexandru
|
|
#include<bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
typedef long long ll;
|
|
typedef pair<ll,ll> pll;
|
|
const ll NMAX=1e5+5;
|
|
ll primes[NMAX],divisors[NMAX],cntp=0,cntdiv=0;
|
|
bool sieve[NMAX];
|
|
void AddDivisors(ll base, ll exponent){
|
|
ll n=cntdiv,curr=1;
|
|
for(ll j=1;j<=exponent;j++){
|
|
curr*=base;
|
|
for(ll i=0;i<n;i++){
|
|
divisors[cntdiv++]=divisors[i]*curr;
|
|
}
|
|
}
|
|
}
|
|
map<ll,ll> cache;
|
|
void tc(){
|
|
ll n,cpy;
|
|
cin>>n;
|
|
if(cache.count(n)){
|
|
cout<<cache[n]<<'\n';
|
|
return;
|
|
}
|
|
cpy=n;
|
|
divisors[0]=1;
|
|
cntdiv=1;
|
|
for(ll i=0;primes[i]*primes[i]<=n;i++){
|
|
ll e=0;
|
|
while(n%primes[i]==0) n/=primes[i],e++;
|
|
if(e) AddDivisors(primes[i],e*2);
|
|
}
|
|
if(n) AddDivisors(n,2);
|
|
ll ans=LLONG_MAX;
|
|
for(ll i=0;i<cntdiv;i++){
|
|
if(divisors[i]>cpy){
|
|
ans=min(ans,divisors[i]);
|
|
}
|
|
}
|
|
cache[cpy]=ans-cpy;
|
|
cout<<ans-cpy<<'\n';
|
|
}
|
|
int main()
|
|
{
|
|
for(ll i=2;i<NMAX;i++){
|
|
if(!sieve[i]){
|
|
primes[cntp++]=i;
|
|
for(ll j=i*i;j<NMAX;j+=i)
|
|
sieve[j]=1;
|
|
}
|
|
}
|
|
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
|
|
ll t; cin>>t; while(t--)
|
|
tc();
|
|
return 0;
|
|
}
|