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

  1. 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 ...

  2. 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 , ...

  3. 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 ...

  4. 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" ...

  5. 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 ...

  6. 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 ...

  7. 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 ...

  8. 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 ...

  9. 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

  1. 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 ...

  2. 【HDOJ】3047 Zjnu Stadium

    Take the right and check the collection . /* 3047 */ #include <iostream> #include <string> #include <map> #include &l ...

  3. 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 ...

  4. 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 ...

  5. 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 ...

  6. 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- ...

  7. 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 ...

  8. Use VMware fictitious linux System environment

    Instructions for operation steps : https://jingyan.baidu.com/album/f71d603782e70e1ab641d1da.html?picindex=1 vmware Clone multiple systems : http ...

  9. 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 ...

  10. 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 . ...