1 /* 2  思路：开始我找出b的所有质因数 复杂度logN的，后来求每个质因数生成的约数即质因数m*（1，2，3...）（复杂度大了）和筛法的思想类似， 3  再sort，再扫一遍找大于a的最小约数，结果T了，在10^7的数据大小时就T了。 4 所以改一下，不需要生成所有的约数，每个质因数只要生成一个大于a的最小约数就可，这样就一共生成了和质因数数目一样多的约数（小于OlogN），再sort即可。 5 */ 6 #include<iostream> 7 #include<cstdio> 8 #include<cstring> 9 #include<string>10 #include<map>11 #include<algorithm>12 #include<set>13 #include<vector>14 using namespace std;15 int a,b,su;16 vector<int>s;17 vector<int>all;18 void solve()19 {20     int temp=b;21     if(a>=temp){ cout<<"-1"<<endl; return; } //特判22     //找质因数：23     for(int i=2;i*i<=temp;i++)24         { if(temp%i==0) { s.push_back(i); while(temp%i==0) temp/=i; } }25     s.push_back(b); // 因为b本身可能就是素数，所以要在vector里加b，就算不是素数，也对结果无影响。26     for(int i=0;i<s.size();i++) //生成s.size()个约数。27     { su=s[i]; int m=a/su+1; all.push_back(su*m); }28     sort(all.begin(),all.end());29     for(int i=0;i<all.size();i++)30         if(all[i]>a)31         {cout<<all[i]-a<<endl;return ;}32 }33 int main()34 {35     freopen("b.txt","r",stdin);36     int T; cin>>T; while(T--) { cin>>a>>b; s.clear(); all.clear(); solve(); } return 0;37 }