/*
* [题意本质]
* 输入n,如果n的约数个数是奇数,输出yes,否则输出no
* (注:n的约数不包括1和n本身,不过包括也不影响奇偶性)
*
* [解题方法]
* 1、最简单普通的做法:
* 枚举i(1<i<=sqrt(n)),累计约数个数,复杂度sqrt(n),结果超时TLE
* 2、素数筛法加速+简单组合数学:
* 约数个数 = 累乘(f(pi)+1),结果AC,1秒左右
* (f(pi)表示n中有多少个pi相乘)
* (组合数学理解:假设有n中3个pi,那么我可以选0个,1个,2个,3个,共4种方法,即f(pi)+1)
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define LL long long
#define M 100005
#define inf 0x3fffffff
int p[9600], vis[M], k;
int main()
{
int cnt, i, j;
LL n; //注意!n需要用longlong
for (i = 2; i < M; i++) //打sqrt(n)内的素数表即可
{
if (!vis[i])
{
p[k++] = i;
for (j = i+i; j < M; j+=i)
vis[j] = 1;
}
}
while (cin >> n, n)
{
cnt = 1;
//p[i]*p[i] <= n 是非常重要的条件!
//因为大于sqrt(n)的素性约数最多只有一个
for (i = 0; i < k && (LL)p[i]*p[i] <= n; i++)
{
if (n % p[i] == 0)
{
int tp = 1;
do
n /= p[i], ++tp;
while (n % p[i] == 0);
cnt *= tp;
}
}
//n>1说明有个比sqrt(n)大的素性约数,不能漏了
if (n > 1) cnt *= 2;
if (cnt & 1) puts("yes");
else puts("no");
}
return 0;
}
分享到:
相关推荐
UVA109的题解,经测试完全正确,还附有题解。
uva272
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
uva_trilearn2002 源代码
PDF试题
主要是uvaoj习题相关题目 练习题目
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
UVA 499 Solution in C/ C++