欢迎光临
我们一直在努力

东方博宜OJ 1140:亲密数对 ← 约数的成对性

【题目来源】 https://oj.czos.cn/p/1140 【题目描述】 键盘输入 N,N 在 2 至 2000 之间,求 2 至 N 中的亲密数对,就是 A 的因子和等于 B,B 的因子和等于 A,且 A≠B。如 48 和 75 是亲密数对。48 的因子和为 2+3+4+6+8+12+16+24=75,而 75 的因子和为 3+5+15+25=48。 【输入格式】 只有一行,为一个整数 N(2≤N≤2000)​​​​​​​ 【输出格式】 输出若干行,每行两个整数(用一个空格隔开)。​​​​​​​ 【输入样例】 200 【输出样例】 48 75 75 48 140 195 195 140​​​​​​​ 【数据范围】 请注意,求出的亲密数对的 2 个数都不应该超过 n 的范围。 【算法分析】 ● 什么是约数?设 a,b 为整数,且 b≠0。若存在整数 k,使得 a=k×b。则称 b 是 a 的约数(因数),记作 b|a。 ● 约数的成对性:对于任意整数 x,如果 i 是 x 的约数,那么 x/i 也是 x 的约数。 证明:已知 i 是 x 的约数,故 x/i 是整数。又因为 x/(x/i)=i 为整数,故根据约数定义,知 x/i 是 x 的约数。 ● 推论:若 x 存在大于 1 的约数,则一定存在一个不超过 sqrt(x) 的约数。 约数成对性在素数判定中的应用:假设 x 是合数,则存在一对约数 (a,b),使得 a×b=x,2≤a≤b。显然,可由 a×a≤a×b=x^2 推出 a≤sqrt(x),即合数 x 必然存在一个不超过 sqrt(x) 的真约数。所以,在素数判定问题中,只需要遍历 2 到 sqrt(x) 之间有没有能整除 x 的数就行,不用一直遍历到 x-1。 ● 关键点说明:题目不包含 1 作为因子,只统计除自身外大于 1 的约数。 【算法代码一】

#include <bits/stdc++.h>
using namespace std;

int factorSum(int x) {
int sum=0;
for(int i=2; i*i<=x; i++) {
if(x%i==0) {
sum+=i;
if(i!=x/i) {
sum+=x/i;
}
}
}
return sum;
}

int main() {
int n;
cin>>n;
for(int a=2; a<=n; a++) {
int b=factorSum(a);
if(b>n) continue;
int t=factorSum(b);
if(t==a && a!=b) {
cout<<a<<" "<<b<<endl;
}
}
return 0;
}

/*
in:
200

out:
48 75
75 48
140 195
195 140
*/

【算法代码二】

#include <bits/stdc++.h>
using namespace std;

int factorSum(int x) {
int sum=0;
for(int i=2; i*i<=x; i++) {
if(x%i==0) {
sum+=i;
if(i!=x/i) {
sum+=x/i;
}
}
}
return sum;
}

int main() {
int n;
cin>>n;
for(int a=2; a<=n; a++) {
for(int b=2; b<=n; b++) {
int sa=factorSum(a);
int sb=factorSum(b);
if(sa==b && sb==a && a!=b) {
cout<<a<<" "<<b<<endl;
}
}
}
return 0;
}

/*
in:
200

out:
48 75
75 48
140 195
195 140
*/

【参考文献】 https://blog.csdn.net/hnjzsyjyj/article/details/161994231 https://blog.csdn.net/hnjzsyjyj/article/details/161995534 https://blog.csdn.net/liunian_curry/article/details/139721281

赞(0)
未经允许不得转载:171主机测评 » 东方博宜OJ 1140:亲密数对 ← 约数的成对性
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址