为什么会WA50？

常规
1

1. 亲和数

XJOI - 题目ID：1365必做题100分

最新提交：

Wrong Answer

50 分

历史最高：

Wrong Answer

50 分

时间限制: 1000ms

空间限制: 65536kB

题目描述

某一天，tenshi看了一本趣味数学书，上面提到了亲和数：定义数对 (x,y) 为亲和数对当且仅仅当x、y为不同正整数，且x、y各自的所有非自身正因子之和等于另一个数。例如 (220,284) 和 (280,224) 都是亲和数对，因为：
220的所有非自身正因子之和为：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
284的所有非自身正因子之和为：1 + 2 + 4 + 71 + 142 = 220
数对 (x,y ) 跟 (y,x) 被认为是同一数对，所以我们只考虑 x任 务 ：tenshi对某个范围内的亲和数对的数量非常感兴趣，所以希望你能帮她编写一个程序计算给定范围内的亲和数对的数量。给定一个范围A到B，如果A≤ x ≤ B，并且 x小于y，则我们称 (x,y)在范围[A,B]内。

输入格式：

从文件的第一行分别读入正整数A和B，其中A、B满足
1 ≤ A ≤ B ≤ 10^8 且 B-A ≤ 5*10^4

输出格式：

输出文件只有一行，就是[A,B]内亲和数对的数量

样例输入：

200 1200

样例输出：

2

数据范围：

见题目

时间限制：

1000

空间限制：

65536

提示：

注：[200,1200] 内的数对只有两个，分别是(220,284)和(1184 1210)
WA50代码（暴力）：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum=0,m;
map<int,int> vis;
map<int,int> vis1;
int f(int x){
	int ans=0;
	for(int i=1;i*i<=x;i++){
		if(x%i==0){
			ans+=i;
			ans+=x/i;
	//		cout<<i<<" "<<x/i<<endl;
		}
	}
	ans-=x;
	return ans;
}
signed main(){
    cin>>n>>m;
    //cout<<f(284);
	for(int l=n;l<=m;l++){
		int cnt=f(l),cnt1=f(cnt);
		if(vis[l]&&vis1[cnt]||vis[cnt]&&vis1[l]){
			continue;
		}
		if(l==cnt) continue;
		if(cnt1==l){
			sum++;
			vis[l]=vis1[cnt]=1;
		//	cout<<l<<" "<<cnt<<endl;
		}
	}
	cout<<sum;
}
2 个赞
2 
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	int ans_=0;
	for(int i=a;i<=b;i++){
		int ans=1;
		for(int j=2;j*j<=i;j++){
			if(i%j==0)
			ans+=j+i/j;
			}
			if(ans<=i)continue;
			int ans2=1;
			for(int j=2;j*j<=ans;j++){
				if(ans%j==0)
				ans2+=j+ans/j;
				}
	    if(ans2==i)
		ans_+=1;
	}
	printf("%d",ans_);				
}
3 个赞