首页 > 代码库 > xtuoj A+B Again（在某个数中找大于m的最小约数）
xtuoj A+B Again（在某个数中找大于m的最小约数）
新生赛：
| 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。
样例输入
3 1 2 1 3 1 4
样例输出
1 2 1
思路：开始我找出b的所有质因数 复杂度logN的，后来求每个质因数生成的约数即质因数m*（1，2，3...）（复杂度大了）和筛法的思想类似，再sort，再扫一遍找大于a的最小约数，结果T了，在10^7的数据大小时就T了。
所以改一下，不需要生成所有的约数，每个质因数只要生成一个大于a的最小约数就可，这样就一共生成了和质因数数目一样多的约数（小于OlogN），再sort即可。
代码如下：
#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; } //特判
//找质因数：
for(int i=2;i*i<=temp;i++)
{
if(temp%i==0)
{
s.push_back(i);
while(temp%i==0) temp/=i;
}
}
s.push_back(b); // 因为b本身可能就是素数，所以要在vector里加b，就算不是素数，也对结果无影响。
for(int i=0;i<s.size();i++) //生成s.size()个约数。
{
su=s[i];
int m=a/su+1;
all.push_back(su*m);
}
sort(all.begin(),all.end());
for(int i=0;i<all.size();i++)
if(all[i]>a) {cout<<all[i]-a<<endl;return ;}
}
int main()
{
int _;
cin>>_;
while(_--)
{
cin>>a>>b;
s.clear();
all.clear();
solve();
}
return 0;
}
xtuoj A+B Again（在某个数中找大于m的最小约数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。