HDU 1999 不可摸数 （模拟）
2024-09-24 21:30:35
Problem Description
s(n)是正整数n的真因子之和，即小于n且整除n的因子和.例如s(12)=1+2+3+4+6=16.如果任何数m，s(m)都不等于n,则称n为不可摸数.
Input
包含多组数据，首先输入T,表示有T组数据.每组数据1行给出n(2<=n<=1000)是整数。
Output如果n是不可摸数，输出yes，否则输出no
Sample Input`
3
2
5
8`
Sample Output`
yes
yes
no`
题目分析：
首先要弄明白不可摸数的概念：任何数m，s(m)都不等于n,则称n为不可摸数而s(m)表示的是数m的真因子之和
然后还要考虑到一点就是说即使当前的数m的值很大，但是m的真因子之和也有可能很小，所以求值时m的值要比实际要求大很多。
这个是完全正确的代码
#include <stdio.h>
int M= 500050;
int moshu[1010];
long long int a[500050];
void qiumoShu()//函数用于求不可摸数
{
int i,j,m;
m = M/2;//虽然要求的m的值小于1000就好，但是即使m很大相对应的s(m)的值可能很小
for (i=1; i<=m; ++i)
for (j=i+i; j<M; j+=i)
a[j] += i;//每个只要是当前i的倍数的值都要加上i
for (i=0; i<M; i++) //吧小于1000的不可摸数都标记出来
if (a[i]<=1000)
moshu[a[i]] = 1;
}
int main ()
{
int a, i, N;
scanf ("%d", &N);
qiumoShu();
while (N --)
{
scanf ("%d", &a);
if (moshu[a])
printf ("no\n");
else
printf ("yes\n");
}
return 0;
}
这个代码错误，明显的思路就解释不通，就是那个标记点的问题，还有就是数组范围太小了开大也肯定会超时的，但是可能是测试数据太弱啦，竟然提交也能过，希望注意一下：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int main()
{
int i,j,n,m,flag=0;//标记放这里就行
int a[5000]= {0};
a[0]=1;
a[1]=1;
for(i=2; i<5000; i++)
{
a[i]=0;
for(j=1; j<=i/2; j++)
if(i%j==0)
a[i]+=j;
}
cin>>n;
while(n--)
{
cin>>m;
//flag=0 //标记如果在这里重置为0的话就WA
for(i=0; i<=1000; i++)
{
if(m==a[i])
{
flag=1;
break;
}
}
if(flag==0) //问题
{
printf("yes\n");
}
else
{
printf("no\n");
}
}
return 0;
}
最新文章
- switch语句的妙用
- variadic function 的使用
- 3个sprint的团队贡献分
- Andorid 6连接Libreswan L2TP VPN
- hbase 使用
- cocos2d-x中CCScale9Sprite的另一种实现
- 最火的.NET开源项目（转）
- PHP中::、->、self、parent::、$this操作符的区别
- prototype/constructor/__proto__之constructor。
- STL容器介绍（转）
- UGUI Button控件
- WIX 学习笔记- 1 简介
- 当try和finally里都有return时，会忽略try的return，而使用finally的return
- 使用HTML DOM 来分配事件 —— onmouseover和onmouseout ，onmousedown和onmouseup
- map和flatmap的区别+理解、学习与使用 Java 中的 Optional
- Pandas 1 表格数据类型DataFrame
- 从零开始学安全(七)●Linux基础命令学习笔记
- 理解mpvue的生命周期
- SpringMVC系列（二）: SpringMVC各个注解的使用
- 彻底解决java WEB项目的文件路径问题(war包)