首页 > 代码库 > 【枚举约数】HackerRank - Week of Code 26 - Satisfactory Pairs
【枚举约数】HackerRank - Week of Code 26 - Satisfactory Pairs
题意：给你一个正整数n，问你存在多少个正整数对a，b(a<b)，满足条件：存在正整数x，y，使得ax+by=n。
就预处理出n以内所有数的约数，然后暴力枚举a，暴力枚举x，然后枚举n-ax的所有约数，判重，统计答案即可。
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<int>::iterator ITER;
vector<int>divisors[300010];
int n,used[300010],ans;
bool cmp(const int &a,const int &b)
{
return a>b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
for(int j=1;j*j<=i;++j)
if(i%j==0)
{
divisors[i].push_back(j);
if(j*j!=i)
divisors[i].push_back(i/j);
}
sort(divisors[i].begin(),divisors[i].end(),cmp);
}
for(int a=1;a<n;++a)//枚举a
for(int x=1;x*a<n;++x)//枚举x
{
int yb=n-x*a;
for(ITER it=divisors[yb].begin();it!=divisors[yb].end();++it)//*it 就是b
{
if((*it)<=a)//因为b>a
break;
if(used[*it]!=a)//防止重复统计
{
++ans;
used[*it]=a;
}
}
}
printf("%d\n",ans);
return 0;
}
【枚举约数】HackerRank - Week of Code 26 - Satisfactory Pairs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。