A+B Again（在某个数中找大于m的最小约数）

A+B Again

Accepted : 15 Submit : 243

Time Limit : 1000 MS Memory Limit : 65536 KB

题目描述

上次趣味赛小明的a+b坑了不少不喜欢思考的同学，小明为了表示歉意，这次出了道简单的a+b给大家当签到题，希望大家能开心刷题。那么，题目来了！！！
求使得b/(a+x)为整数的最小正整数x的值。

输入

第一行是一个整数K（K≤10000）,表示样例的个数。以后每行一个样例，为两个正整数a,b(1≤a,b≤108)。

输出

每行输出一个样例的结果，如果不存在这样的x，输出-1。

样例输入

1 2

1 3

1 4

样例输出

高手的思路：开始我找出b的所有质因数复杂度logN的，后来求每个质因数生成的约数即质因数m*（1，2，3...）（复杂度大了）和筛法的思想类似，
再sort，再扫一遍找大于a的最小约数，结果T了，在10^7的数据大小时就T了。
所以改一下，不需要生成所有的约数，每个质因数只要生成一个大于a的最小约数就可，这样就一共生成了和质因数数目一样多的约数（小于OlogN），再sort即可。

ACKNOWLEDGE:　　　　http://94it.net/a/jingxuanboke/2015/0112/446788.html

 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 }

队列