本文主要是介绍hdu1286 找新朋友，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
问题如上
在这个题目上耗费了一下午加一晚上的时间。。= =真是略显水。
考虑了很多。。最终正确的代码如下：
#include <iostream>
#include <cstring>
#define max 32768
using namespace std;int p;
bool num[32768];
short cal[32768];
short prime[32768];
bool current[32768];int cm(int a, int b);//求公约数并返回最小公约数，b不是素数
void GetPrime();int main()
{int cn, i, no, cur, j;GetPrime();cin >> cn;while(cn --){memset(current,1, sizeof(current));cin >> cur;if(num[cur])cal[cur] = cur - 1;else{no = 1;for(i = 0; i < p && prime[i] < cur; i++){if(cur % prime[i] == 0)for(j = prime[i]; j <= cur; j += prime[i]){current[j] = false;}}for(i = 2; i <= cur; i++){if(current[i])no++;}cal[cur] = no;}cout << cal[cur] << endl;}return 0;
}
void GetPrime()
{int i, j, temp;memset(num, 1, sizeof(num));p = 2;prime[0] = 2;prime[1] = 3;for(i = 1; i <= 3; i++)num[i] = true;for(i = 4; i <= 32768; i++){if(num[i]){for(j = 0; j < p; j++){if(i % prime[j] == 0){num[i] = false;temp = i;while(temp <= 32768){num[temp] = false;temp += i;}break;}}if(num[i])prime[p++] = i;}}
}一开始考虑到了各种问题。发现了如下问题：
1.数组下标不正确，与上方不相对应
2.对于sizeof理解不深刻，以及储存空间不够深刻，造成开始的memory溢出;
3.筛法原来就是开一个bool型的数组，然后从里面去除。计算素数的时候使用了筛法。（但是我一直不知道- -）;
4.打表的方法可以用于数据量大并且可能有重复的情况。
5.建立全局变量以后里面的值如果并未初始化，存的全部是0.起码int，short，bool型是这个样子。
算法分析：
先求出在该范围的素数，然后求出输入数字的素数因子，使用筛法计算非素数数量。
本题设计到了最小公约数，素数。该题是一道水题，完全可以不计算所有的素数来求出。。但是我还是球了- -。
附加筛法代码，转载自：点击打开链接
//筛选法处理
#include <stdio.h>
#include <string.h>
char hash[32770]; //使用字符型的减少了内存的开销int main()
{int i,j,t,n,count;while(scanf("%d",&t)!=EOF){while(t--){scanf("%d",&n);memset(hash,0,sizeof(hash)); //每次都要赋初始值count = 0;for(i=2;i<=n;i++){if(n%i==0)for(j=i;j<=n;j+=i) // 这里是用了筛选法，注意的是j=i为初始条件 ，而不是j=i+i；hash[j] = 1;}for(i=1;i<=n;i++) if(hash[i]==0)count++;printf("%d\n",count);}}return 0;
}
#include <stdio.h>
int ans;
void Eu(int n){for(int i = 2; i * i <= n;++i){if(!(n%i)){ans *= i - 1;n /= i;while(!(n%i)){ans *= i;n/=i; } }}if(n > 1){ans *= n -1;}return ;
}
int main(){int n,test_case;scanf("%d",&test_case);while(test_case--){scanf("%d",&n);ans = 1;Eu(n);printf("%d\n",ans);}return 0;
}这篇关于hdu1286 找新朋友的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
