题目：求两个大数之间的所有公因数，a，b<=1e13
思路：
先求出最大公因数temp，a和b的其他因数一定是最小公倍数的因数。
这个时候就转换成了枚举temp所有的因数
i*j==temp,...
题目：求两个大数之间的所有公因数，a，b<=1e13
思路：
- 先求出最大公因数temp，a和b的其他因数一定是最小公倍数的因数。
- 这个时候就转换成了枚举temp所有的因数
- i*j==temp,我们枚举i就可以了，j=temp/i。（只用枚举i到sqrt(temp)）
- 将所有的数存在数组里面，sort。（当然也可以直接用set）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define res register int
const int maxn=1e5;
int ans=0;
ll c[maxn];
ll gcd(ll a,ll b)
{
ll temp1=1,temp2=1;
while(temp1){
temp1=a%b;
temp2=a/b;
a=b;
b=temp1;
}
return a;
}
int main()
{
ll a,b;
scanf(\"%lld%lld\",&a,&b);
ll temp=gcd(a,b);
c[++ans]=1;
ll i=100;
for(i=2;i*i<temp;i++){
if(0==temp%i){
c[++ans]=i;
c[++ans]=temp/i;
}
}
if(1!=temp) c[++ans]=temp;
if(i*i==temp) c[++ans]=i;
sort(c+1,c+ans+1);
for(res i=1;i<=ans;i++){
printf(\"%lld \",c[i]);
}
return 0;
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
