**A+B Again**

**Accepted : 15 Submit : 243**

**Time Limit : 1000 MS Memory Limit : 65536 KB **

Title Description

Xiaoming's in the last fun contest a+b A lot of students who don't like to think , Xiao Ming apologizes , This time there was a simple a+b Check in for everyone , I hope you can brush the topic happily . that , Here comes the title ！！！

To make b/(a+x) Is the smallest positive integer of an integer x Value .

Input

The first line is an integer K（K≤10000）, Represents the number of samples . One sample for each line in the future , For two positive integers a,b(1≤a,b≤108).

Output

Output the result of one sample per line , If it doesn't exist x, Output -1.

The sample input

3

1 2

1 3

1 4

Sample output

1

2

1

Master's idea ： I started to find out b All prime factors of Complexity logN Of , Later, we find the divisor of each prime factor, which is the prime factor m*（1,2,3...）（ It's more complicated ） It's similar to the idea of sieving ,

Again sort, Scan again to find a The least divisor of , result T 了 , stay 10^7 When the data size is small T 了 .

So let's change that , You don't have to generate all the divisors , Each prime factor only needs to generate one greater than a The least divisor of can be , In this way, as many divisors as the number of prime factors are generated （ Less than OlogN）, Again sort that will do .

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

/*

Ideas ： I started to find out b All prime factors of Complexity logN Of , Later, we find the divisor of each prime factor, which is the prime factor m*（1,2,3...）（ It's more complicated ） It's similar to the idea of sieving ,

Again sort, Scan again to find a The least divisor of , result T 了 , stay 10^7 When the data size is small T 了 .

So let's change that , You don't have to generate all the divisors , Each prime factor only needs to generate one greater than a The least divisor of can be , In this way, as many divisors as the number of prime factors are generated （ Less than OlogN）, Again sort that will do .

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<algorithm>

#include<set>

#include<vector>

using namespace std;

int a,b,su;

vector<int>s;

vector<int>all;

void solve()

{

int temp=b;

if(a>=temp){ cout<<"-1"<<endl; return; } // Special judgement

// Looking for quality factor ：

for(int i=;i*i<=temp;i++)

{ if(temp%i==) { s.push_back(i); while(temp%i==) temp/=i; } }

s.push_back(b); // because b It could be prime in itself , So we need to vector Riga b, Even if it's not prime , It also had no effect on the results .

for(int i=;i<s.size();i++) // Generate s.size() A divisor .

{ su=s[i]; int m=a/su+; all.push_back(su*m); }

sort(all.begin(),all.end());

for(int i=;i<all.size();i++)

if(all[i]>a)

{cout<<all[i]-a<<endl;return ;}

}

int main()

{

freopen("b.txt","r",stdin);

int T; cin>>T; while(T--) { cin>>a>>b; s.clear(); all.clear(); solve(); } return ;

}

queue

## A+B Again（ Find a number greater than m The least divisor of ） More articles about

- ytu 1061: Find the largest number out of three （ Water problem , Template function exercise + Macro definition exercise ）
1061: Find the largest number out of three Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 154 Solved: 124[Submit][Status][We ...

- Massive data processing - 10 Find the largest of the billion 10000 Number （top K problem ）
The first two days of the interview 3 Mr. Mian asked me this question ( Want to say TEG Of 3 All the interviewees are very kind , Hope to finish the last one , Due to various reasons, I can't help but want to go to the goose farm ), It's better to build a minimum heap . First take 10000 Build a pile of numbers , ...

- hdu 1258 from n The sum of the numbers is t The combination of (DFS)
The question : First of all, I'll give you a t, And then there was n, Type in n Number , And then you ask for n The sum of the numbers is t How many sequences are there in all , Put them in left to right order . Sample Input4 6 4 3 2 2 1 15 3 2 1 1 ...

- poj2578--- The first of three numbers is greater than 168 Of
#include <stdio.h> #include <stdlib.h> int main() { int a,b,c; scanf("%d %d %d" ...

- Find... In the mass data top K project
1. 10 Find the largest of the billion 1000 Number This kind of problem is divide and conquer + Heap sort . Why divide ? Because there are so many , It's not enough to load it all into memory , So it's distributed to multiple machines , Or multiple files , But how many shares are there , As the case may be , As long as the memory is satisfied ...

- A classic interview question ： How to go from N Choose the largest of the numbers （ Small ） Of n Number
Reprint :https://zhidao.baidu.com/question/1893908497885440140.html I've been thinking about this for almost a year , I've discussed it with a lot of people . According to the information I got ,Goo ...

- Xiaoyi invites you to play a number game , Xiaoyi gives you a series of integers . You two play games with these integers . Every time Xiaoyi says a number at will , Then you need to select a part of the series of numbers to make their sum equal to the number Xiaoyi said . for example ： If {2,1,2,7} It's a series of numbers that you have , The number Xiaoyi said is 11. You can get the solution 2+2+7 = 11. If the naughty Xiaoyi wants to pit you , The number he said was 6, So you can't piece it together for 6 Now Xiaoyi gives you n Number , Let you find out what you can't get from n Choose part of the number to sum
Xiaoyi invites you to play a number game , Xiaoyi gives you a series of integers . You two play games with these integers . Every time Xiaoyi says a number at will , Then you need to select a part of the series of numbers to make their sum equal to the number Xiaoyi said . for example : If {2,1,2 ...

- Find the sum of several numbers in the array equal to a certain number [LeetCode]
First of all, make it clear , This aspect of the problem design to the knowledge point is the array search problem . There are three specific solutions to similar search operations : 1. The brute force algorithm , Multiple for loop , High time complexity 2. Prioritize , And then it's left and right , But it does ...

- 3sum( Find the sum of three numbers in the array as 0)
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all un ...

## Random recommendation

- s1=s1+1 And s1+=1 The difference between
I just saw an interview question , The title is like this :short s1=1;s1=s1+1; What's wrong with it? ?short s1=1;s1+=1; What's wrong with it? ? At first glance, it was s1=s1+1 and s1+=1 The difference between . In development, we basically use the latter ...

- 【HDOJ】3047 Zjnu Stadium
Take the right and check the collection . /* 3047 */ #include <iostream> #include <string> #include <map> #include &l ...

- symfony Installation
Symfony It's based on MVC Of PHP frame , The latest version is 2.7 working principle Synfony Two ways to install 1. Use composer Installation 1) download composer http://getcomposer ...

- HDU 2254 Olympic （ number theory + matrix ）
The title is not explained in Chinese . .. It's important to note that : In Discrete Mathematics , Adjacency matrix of digraph A Indicates that the path length between all points is 1 Number of paths for ,A^n The path length is n Number of paths for . Therefore, it is necessary to require that two points be in (A^t1)~(A^t2) Number of paths for ...

- 201521123089 《Java Programming 》 The first 3 Weekly learning summary
1. This week's learning summary Learning object-oriented , I will learn a lot of fragmented concepts and knowledge . Try to learn how to use mind maps to break up these concepts . Knowledge is organized . Please use pen and paper or the following tools to draw the knowledge points learned this week . Take a picture or upload it . 2. In writing ...

- apt download open-jdk8 Report errors add-apt-repository: command not found
Download today jdk8 Report errors stay Ubuntu Next , From time to time there's this mistake . add-apt-repository: command not found sudo apt-get install software- ...

- C# Read xml——XmlReader and XElement
1. There are some xml The document header has DTD, An error will be reported when parsing the program Such as : Other information : Open the outside DTD“file:///E:/PM data /MeContext=CDF2775/MeasDataCollection.dtd ...

- Use VMware fictitious linux System environment
Instructions for operation steps : https://jingyan.baidu.com/album/f71d603782e70e1ab641d1da.html?picindex=1 vmware Clone multiple systems : http ...

- SpringBoot Start source code exploration ---listeners.starting()
1. First call starting() Method , Its interior is one to all listener Of starting() Called for loop , Then each listener Call another starting Method , Its internal call multicastEv ...

- python String splicing methods
python There are several ways to splice strings : 1. Directly through (+) Operator splicing s = 'Hello'+' '+'World'+'!' print(s) Output results :Hello World! This is the most common way . ...